Test point for its position relative to the convex hull in log(n)

Question

I have a collection of 2D points S and I need to test if an input point q is inside or outside the convex hull of S.

Since it's about a binary decision, I was thinking I could theoretically achieve O(log(N)) by using a decision tree.

However I have no idea how to organize the data and how the algorithm would look like to really get an answer in O(log(N)).

While researching with this idea in mind, I've found this:

How can we find these two cases more quickly? Binary search. Just search for x in the first coordinates of points in the two chains. If it is in the chain, you have found a crossing through a vertex (and you don't have to be as careful to tell what kind of crossing, either). If x is not the coordinate of a vertex in the chain, the two nearest values to it tell you which segment the ray from (x,y) might cross. So we can test whether a point is in a convex polygon in time O(log n).

It turns out that there are data structures that can test whether a point is in an arbitrary polygon (or which of several polygons it's in) in the same O(log n) time bound. But they're more complicated, so I don't have time to describe them here; I'll talk about them at some point in ICS 164.

(http://www.ics.uci.edu/~eppstein/161/960307.html)

So do you have any ideas:

1. How the data structure should look like to get it down in O(log(N))?
2. How the algorithm should look like?

Answer 1

Let's deal with only one chain first. We want to check whether (qx, qy) is above a convex chain of line segments.

The expensive part is is binary searching on a list of x coordinates to find the biggest one less than your query point. All you need for this is an array of the points of the chain sorted in x order. Then it's a simple "point above line?" test.

Now we want to see whether a point is in a convex polygon. If you represent the edges of that convex polygon as an upper chain and a lower chain, then it's the intersection of the stuff below the upper chain with the stuff above the lower chain. So it's two binary searches.

(Even if you've just got the points in clockwise sorted order or something, you can find the smallest and largest x coordinates in the polygon in logarithmic time using binary search or four-point search. So you don't even have to precompute the upper and lower chains if you don't want to.)

EDIT: I see that your question can also be parsed as "what do point location data structures look ilke?" rather than "how do I store the convex hull to permit efficient inside/outside testing?"

It is natural to study point location in a slightly more general context than inside-outside testing. There is a

CGAL can do point location in a couple of different ways. It's written by smart people with a good understanding of the algorithms they're implementing and the computers the algorithms are going to use. You probably won't be able to find anything too much faster that still works correctly.

With that said, Haran and Halperin compared the performance of CGAL's various algorithms. They used a modern computer as of 2008 and they made up a lot of test data and tried CGAL's different point location strategies on each test case. Among other things, they have a case of about 1.4 million randomly-placed edges where their best data structure only needs about 190 microseconds to answer a point location query.

This is very fast considering the complexity of typical point location algorithms --- I couldn't do that myself. And the theory tells us that it grows like O(log n). However, that O(log n) is several orders of magnitude slower than the O(log n) time it takes to search a sorted array. Bear that in mind when you do computational geometry; the constants matter and they're often not very small.

Answer 2

This problem can be categorized as a classic point-location problem.

• The preprocessing would include calculating convex hull for the set of points, and the line segments of the convex hull would be used in the next step (or the whole of CH as a region).

• There are many standard O(log n) query-time algorithms for this kind of problems (http://en.wikipedia.org/wiki/Point_location) like Kirkpatrick triangulation, randomized trapezoidal maps, etc..

Also note that in expectation, the number of points in CH(S) is O(log N) where N is the number of total points in S. So the number of line segments considered for point location is already reduced to O(log N), which means that the query time is actually O(log log N) in expectation (in terms of total points in S).