Finding the point with minimum x-ordinate, lying between two y-ordinates
Not unless you assume something more. Without further assumptions, if you don't check all $n$ values, the minimum can be some of the unchecked points.

If you know there is just one minimum in (sorted) range, a variant of binary search (the minimum is the point where $x_{k - 1} &gt; x_k &lt; x_{k + 1}$ or one of the endpoints; if $x_k &gt; x_{k + 1}$ the minimum is to the right, and so on) gets it in time $O(\log n)$.