Determine whether a point lies in a convex hull in O(log n) time

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(logn) time, nor can I come up with one myself.Let a[] be an array containing the vertices of the convex hull, can I pre-process this array in anyway, to make it possible to check if a new point lies inside the convex hull in O(logn) time.

Answer 1

Looks like you can.

1. Sort vertices in a[] by polar angle relative to one of vertices (call it A). O(N log N), like convex hull computation.
2. Read point, determine its polar angle. O(1)
3. Find two neighbor vertices, one of them should have polar angle less than point from step 2, and other should have angle bigger (B and C). O(log N), binary search
4. Then simple geometry: draw the triangle between points from A, B, C and check if point from step 2 lies inside. O(1)