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

1 Answer 1

Reset to default
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$
5
  • $\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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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.