Star-shaped polygon

Not to be confused with Star polygon.
A star-shaped polygon (top). Its kernel is shown at the bottom in red.

A star-shaped polygon is a polygonal region in the plane that is a star domain, that is, a polygon that contains a point from which the entire polygon boundary is visible.

Formally, a polygon P is star-shaped if there exists a point z such that for each point p of P the segment zp lies entirely within P.[1] The set of all points z with this property (that is, the set of points from which all of P is visible) is called the kernel of P.

If a star-shaped polygon is convex, the link distance between any two of its points (the minimum number of sequential line segments sufficient to connect those points) is 1, and so the polygon's link diameter (the maximum link distance over all pairs of points) is 1. If a star-shaped polygon is not convex, the link distance between a point in the kernel and any other point in the polygon is 1, while the link distance between any two points that are in the polygon but outside the kernel is either 1 or 2; in this case the maximum link distance is 2.

Examples

Convex polygons are star shaped, and a convex polygon coincides with its own kernel.

Regular star polygons are star-shaped, with their center always in the kernel.

Antiparallelograms and self-intersecting Lemoine hexagons are star-shaped, with the kernel consisting of a single point.

Visibility polygons are star-shaped as every point within them must be visible to the center by definition.

Algorithms

Testing whether a polygon is star-shaped, and finding a single point in the kernel, may be solved in linear time by formulating the problem as a linear program and applying techniques for low-dimensional linear programming (see http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf, page 16).

Each edge of a polygon defines an interior half-plane, the half-plane whose boundary lies on the line containing the edge and that contains the points of the polygon in a neighborhood of any interior point of the edge. The kernel of a polygon is the intersection of all its interior half-planes. The intersection of an arbitrary set of N half-planes may be found in Θ(N log N) time using the divide and conquer approach.[1] However, for the case of kernels of polygons, a faster method is possible: Lee & Preparata (1979)[2] presented an algorithm to construct the kernel in linear time.

See also

References

  1. 1 2 Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3.
  2. ↑ Lee, D. T.; Preparata, F. P. (July 1979), "An Optimal Algorithm for Finding the Kernel of a Polygon", Journal of the ACM, 26 (3): 415–421, doi:10.1145/322139.322142
This article is issued from Wikipedia - version of the 10/11/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.