Finding a point above the line in $O(\log n)$

Question

I am trying to solve the following problem. So far with no success.

Let $S$ be a set of $n$ points in the plane. Preprocess $S$ so that, given a (non-vertical) line $l$, one can determine whether there is any point of $S$ above $l$ in time $O(\log n)$. Few details: preprocess $S$ without knowing line $l$ in advance. Preprocessing doesn't have any special requirements.

According to big-$O$ requirement $O(\log n)$ the determination should be implemented similarly to binary search.

I have considered few options, $y$ - coordinate, slopes, but in any case it seems not relevant.

If you have any idea, I will appreciate sharing it with us.

Thanks!

Answer 1

Find those among the given points that are the on the the upper boundary of the convex hull of $S$, and sort them by they $x$ coordinate. (Any point that is not on this upper boundary can be ignored). Then you should be able to do a binary search along these lines:

Given $l$, check it against the middle point. If the middle point is above $l$, you're done. Otherwise compare the slope of $l$ with the average of the slopes of the two segments of the upper boundary that adjoin the point you just compared to. If the slope of $l$ is greater, then any point of $S$ above $l$ must be somewhere to the left of the middle point; if the slope if $l$ is smaller, then any point above $l$ must be to the right of the middle point.

Now you have reduced the number of points to consider to half of the original size. Proceed by induction.

Answer 2

What are you allowed to do during preprocessing, and how quickly must it be done?

For example, you could compute the residual from each point to the line in $O(n)$ time, and then sort them in $O(nlog(n))$ time, in which case, determining whether or not there is a point of $S$ above the line $l$ is merely an $O(1)$ process - look at the largest residual and see if it is positive or not. Must the preprocessing be done in $O(logn)$ time as well?

Answer 3

Find the Convex Hull in O(nlogn), and for every point on it remember the slope of the segment between it and the next on the convex hull. then, (they are already sorted), given any line l with a slope m, binary search the slope in the slope array. then you only have to check the point before and after m in the array and determine if they're above the line. i'm pretty sure you can't do any better than O(nlogn), although i have no proof of a lower bound.