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?
Asked
Active
Viewed 398 times
1
user1760791
- 113
- 3
2 Answers
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.)
-
Thank you for your help! I apologise for my ignorance, but I am not sure what you mean by algebraic distance... I've tried looking it up but that just resulted in more confusion. So the pre-processing would just include finding the convex hull? Thanks again for your time! – user1760791 Jan 08 '20 at 18:19
-
Distance with sign. Yes, convex hull is enough. – Jan 08 '20 at 18:42
0
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$.
Smokesick
- 1
- 1