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!