Repeated point in polygon: preprocessing complexity given logarithmic query time?

Question

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.

Answer 1

Your problem is a special case of planar point location. The algorithm/data structure you found by Snarak and Tarjan can answer point location (and thus point in polygon) queries in $O(\log n)$ time using $O(n \log n)$ preprocessing and $O(n)$ space. That is optimal. There are two other data structures that achieve this: a data structure by Kirkpatrick and a randomized incremental approach. The randomized incremental approach can be improved to $O(n \log^* n)$ expected preprocessing time in case of a simple polygon, and is fairly simple besides.

Answer 2

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.

Answer 3

I have an algorithm O(log(n)) for this purpose that uses a kind of special data structure that sorts the sides of the polygon when is being created to avoid preprocessing. This sort procedure is executed in O(n*log(n)).