Efficient data-structure for half-plane queries (2D) Given a set of 2D points _P_ with no three points that are colinear, no two points have the same _x_ -coordinate, and no two points have the same _y_ -coordinate. Is there a data-structure with `O(log n)` query time that I can use to test, given a half-plane _h_ , if any points of _P_ are in _h_?

@Smokesick's idea of using the convex hull is a good one. There is no need to use a binary tree, just the convex polygon is enough. The algebraic distance of the vertices to the boundary of the half-plane is a unimodal function and you can find the extrema in logarithmic time.

A practical way is to consider the difference between the distances of successive vertices, and find where they change sign, by dichotomic search. (You can also solve the problem optimally by an adaptation of Fibonacci search, but the extra complexity of the algorithm isn't really worth the fuss.)