Finding the point with smallest x-ordinate between two given y-ordinates


Given a set of points P=p1,p2,..pn in R2 in where pi=(xi,yi),finding the point with smallest x-ordinate having y-ordinates between y1 and y2, where y1 and y2 are given as inputs. I can compare the point with other points which gives me an O(n) time algorithm ? Can this be improved any further ?