A star-shaped polygon (not to be confused with star 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. 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.
Convex polygons are star shaped, and a convex polygon coincides with its own kernel.
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. However, for the case of kernels of polygons, a faster method is possible: Lee & Preparata (1979) presented an algorithm to construct the kernel in linear time.
- 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.
- 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