World's most popular travel blog for travel bloggers.

# [Solved]: Repeated point in polygon: preprocessing complexity given logarithmic query time?

, ,
Problem Detail:

I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is not necessarily simple. I am interested in the case where a polygon has many edges.

Let $n$ be the number of vertices of the polygon. I have an algorithm that performs the online phase in $O(\log n)$ time but the preprocessing phase requires $O(n^3)$ time and space in general, $O(n^2)$ time and space for simple polygons, and $O(n)$ time for star-shaped polygons.

Can we do better? Specifically, does anyone know lower or upper bounds, constructive or not, for the preprocessing phase given $O(\log n)$ query time?

I'm working in two dimensions, and the points have floating point coordinates (i.e., not integer coordinates).

My algorithm is similar to a standard algorithm and has similar performance characteristics. I discovered it independently so it differs in some immaterial ways but it's not original. It works as follows:

Preprocessing:

1. Translate polygon into first quadrant. (This is to simplify later calculations but isn't strictly necessary.)
2. Create a ray passing from the origin through every endpoint and intersection point of an edge. In each resulting cone no edge crosses another.
3. For each cone, sort the edges crossing that cone by their distance from the origin.

Online:

1. Apply the same translation to the query point as was applied to the polygon.
2. Using binary search, find the cone containing the point, or if none, return false.
3. Using binary search, find the number of edges in the point's cone for which the point and origin are on the same side. Return whether this number is odd.

#### Answered By : Solomonoff's Secret

I am posting this answer because Noinia's answer does not account for how the input size changes when reducing Repeated Point In Polygon to Planar Point Location.

Sarnak's and Tarjan's paper Planar Point Location Using Persistent Search Trees solves a related problem, the Planar Point Location problem, with $O(n)$ space, $O(n \log n)$ preprocessing time, and $O(\log n)$ query time. We can reduce Repeated Point In Polygon to Planar Point Location by first computing all edge intersections of the input polygon and passing all the vertices and edge intersections to the Planar Point Location algorithm. In the worst case this reduction grows the input size from $\theta(n)$ to $\theta(n^2)$ and thus Sarnak's and Tarjan's algorithm yields $O(n^2)$ space, $O(n^2 \log n)$ preprocessing time, and $O(\log n)$ query time.

The space and preprocessing time of the above algorithm are likely not optimal because they don't take advantage of the special structure of the intersection points with respect to the vertices.