Determine whether a point lies in a convex hull of points in O(logn)

Question

I've researched several algorithms for determining whether a point lies in a convex hull, but I can't seem to find any algorithm which can do the trick in O(log n) time, nor can I come up with one myself. Let a[] be an array containing the vertices of the convex hull, can I preprocess this array in anyway, to make it possible to check if a new point lies inside the convex hull in O(log n) time?

Answer 1

This is a classic problem in computational geometry, called Polygon Inclusion Problem. Further, you are considering its special case --- Convex Inclusion.

In chapter 4 of this thesis by Michael lail Shamos 1978, you will find that:

Generally,

Theorem 4.2 (Page 92): Whether a point is interior to a simple $n$-gon can be determined in $O(n)$ time, without preprocessing.

and for convex polygon,

Theorem 4.3 (Page 95): The Inclusion question for a convex $n$-gon can be answered in $O(\log n)$ time and $O(n)$ space, given $O(n)$ preprocessing time.

The proofs of these two theorems contain the algorithms you are looking for.

Answer 2

You can

• Find a point that is within the convex hull (find centroid of 3 non-collinear points will do).

• Turn all points into polar coordinate using that one point as origin.

• Now if you have sorted all points using their angle in polar coordinate, you can find 2 points with angle immediately below and above the angle of the point in question.

• Check if the line segment between those 2 points and the line segment connecting the origin and the point in question intersects. If they do, the point is outside the convex hull. If they don't, the point is inside the convex hull

Finding 2 reference points from the sorted list is $O(\log n)$, checking for intersection is $O(1)$, so total time is $O(\log n)$. This does not count the sorting and polarization time just like you allow in the question.