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

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!

-
This seems strange, consider this problem in one less dimension - i.e given a set of points in $\mathbb{R}$ determine in $O(logn)$ if there is a point in this set which is the same as the given point. this of course means searching the set which can not be done without some assumption such as $S$ being sorted – Belgi Apr 17 '12 at 17:56
@HenningMakholm: My thought (a poor one) was that some point of the line will have lower $y$ coordinate than some points of $S$ and I would just answer yes. That is not usually the interpretation. – Ross Millikan Apr 17 '12 at 18:15

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.

-
Henning Makholm, Thank you very much for the answer, how it can be extended to the segment instead of line. Let's say now instead of line $l$ we have a segment, of course x coordinates of point must lie between x coordinates of the endpoints of e. – com May 25 '12 at 5:14

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?

-
For the question to make sense, I think the preprocessing has to be done without knowing $l$. – Henning Makholm Apr 17 '12 at 17:58
yes, on the step of preprocessing we don't know what's line $l$ – com Apr 17 '12 at 18:01

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.

-