Efficient data-structure for half-plane queries (2D)

Question

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?

Answer 1

@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.)

Answer 2

Consider storing the convex hull of $P$ in a binary search tree sorted by edge slope. You can query the data structure by half-plane slope to find a suitable vertex to test if it lies in $h$.