2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I've never heard the term "division wedge". $\endgroup$ – JeffE Jun 5 '12 at 14:45
  • 1
    $\begingroup$ @JeffE: Isn't that a Pink Floyd album from the mid 90s? $\endgroup$ – Dave Clarke Jun 5 '12 at 15:11
  • $\begingroup$ 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. $\endgroup$ – JeffE Jun 5 '12 at 21:58
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – com Jun 5 '12 at 19:04
  • $\begingroup$ 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"? $\endgroup$ – JeffE Jun 5 '12 at 21:59
  • $\begingroup$ @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). $\endgroup$ – jmad Jun 5 '12 at 22:05
  • $\begingroup$ @jmad: The real problem is properly defining what it means to be "inside" a non-simple polygon. Do you mean non-zero winding number? Positive winding number? Odd winding number? Unable to move to infinity without crossing the polygon? All four options yield different results. $\endgroup$ – JeffE Jun 6 '12 at 14:48
  • $\begingroup$ @JeffE: sure but I meant to say that knowing that a polygon is simple won't improve the complexity. (We can discuss in chat) $\endgroup$ – jmad Jun 6 '12 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.