Star-shaped polygon

A star-shaped polygon (not to be confused with star polygon) is a polygonal region in the plane which is a star domain, i.e., 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".cite book
author = Franco P. Preparata and Michael Ian Shamos | title = Computational Geometry - An Introduction | publisher = Springer-Verlag| year = 1985 | id = 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6]

The set of all points "z" with the described property is called the kernel of "P".

Uses

Star-shaped polygons are of interest in computational geometry and its applications such as motion planning because of its relation to the notion of visibility: the star-shaped polygon may be informally defined as the one whose whole interior is visible from a single point, assuming that the polygon boundary is not transparent.

Properties

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

Point-in-polygon queries may be answered in logarithmic time after linear-time preprocessing.

Kernel

Each edge of a polygon defines an interior half-plane, informally defined as a half-plane that contains interior points of the polygon in the vicinity of the edge in question. The kernel of a polygon is the intersection of all its interior half-planes. Intersection of "N" arbitrary half-planes may be found in Θ("N" log "N") time using the divide and conquer approach. Lee and Preparata [Lee, D. T., Preparata, F.P. (1979) "An Optimal Algorithm for Finding the Kernel of a Polygon", Journal of the ACM, Volume 26 , Issue 3 Pages: 415 - 421 ] presented an algorithm to construct the intersection of interior half-planes in optimal Θ("N") time.

ee also

*Visibility polygon
*Monotone polygon

References