# Point Location Problem in Polygon in Repetitive Mode for a Simple Polygon

I consider Point Location Problem in Polygon in repetitive mode in the case of simple polygon.

In computational geometry,Point Location Problem in Polygon problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon.

There are few method that work in Single-Shot approach, where the input is a polygon $P$ and a single point $q$ (no preprocessing time). Ray casting algorithm is the famous algorithm for single-shot, it takes $O(n)$ to determine whether a point $q$ belongs to polygon $P$.

In addition, there is a repetitive approach, where instead of single point $q$ we should check the sequence of points, therefore the preprocessing is required. Division wedge is a algorithm that works in repetitive mode. Query time of division wedge is $O(\log n)$ and preprocessing time is $O(n)$. Division wedge assumes that there is a central point in polygon, visible from every vertex of polygon (part of the kernel of the polygon). The problem is a central point can be easily determined in convex polygon as well as in star-shaped polygon, but what to do in the case of simple polygon.

If division wedge is applied in the case of simple polygon how we can determine a central point in simple polygon? If division edge in not applied if there is the more efficient way to solve a problem in simple polygon than in arbitrary planar subdivision.

• I've never heard the term "division wedge". Jun 5, 2012 at 14:45
• @JeffE: Isn't that a Pink Floyd album from the mid 90s? Jun 5, 2012 at 15:11
• No such thing. Pink Floyd ceased to exist in the mid-80s, right around the time that computational geometers definitively solved the point-location problem. Jun 5, 2012 at 21:58

First question:

By (my interpretation of the) definition, a "central point" exists if and only if the polygon is star-shaped; this condition can be tested in $Θ(n)$ time. So the only thing you can do is run this algorithm, apply division wedge if you find a non-empty kernel, and apply another algorithm if you find an empty kernel.

• thank you very much for your answer, if it's not a star-shaped polygon but it's known to be simple polygon, do we have a better algorithm than for the general planar subdivision?
– com
Jun 5, 2012 at 19:04
• Considering that the point location problem can be solved in general planar subdivisions in $O(\log n)$ query time using $O(n)$ space, both of which are optimal, what do you mean by "better"? Jun 5, 2012 at 21:59
• @fog The restriction "simple" is not that strong for a polygon. You can use techniques of point location that are already in $O(\log n)$ query time (even for non-simple polygons, I believe).