I consider Point Location Problem in Polygon in repetitive mode in the case of s

Question

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(logn) 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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.