determine if a given point is inside the polygon

Question

Given a convex polygon as a counter-clockwise list of n vertices, give O(lgn) algorithm to determine if a given point is inside the polygon. Assume the basic operations take O(1).

I am think a direction that: if a point is inside a convex polygon, what is the special relationship among the points and all the vertecies or edges? Also, I am guessing the trick here is the convex polygon which makes the algorithm lgn.

Answer 1

The only solution for this problem I know of requires O(n) polygon preprocessing time. Afterwards each query point against a preprocessed polygon is handled in O(lg n) time.

Just take a point P inside the polygon (let's call it "pole") and for each vertex draw a ray exiting from P and passing through the vertex. Consider this to be a polar coordinate system with origin at P, with the entire polar plane subdivided into sectors by these rays. Now, given your query point, you just need to convert it to polar coordinates with origin at our pole P. Then just perform binary search to determine the specific sector that contains the query point. The final inside/outside check within the sector (point vs. edge side test) is a trivial O(1) operation. Each query is handled in O(lg n) time needed for binary search.

This approach will actually work with a larger class of polygons than just convex ones. It covers the class of so called star-shaped polygons, i.e. polygons that have a point from which the whole interior of the polygon can be "seen" or "observed".

The O(n) preprocessing time comes from the need to determine the location of the pole in advance.

P.S. I got to carried away thinking about more general case. If your polygon is convex, you can simply use any of its vertices as the pole. That way you get a O(lg n) algorithm right away, no preprocessing required.