Star-shaped polygon
From Wikipedia, the free encyclopedia
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.[1]
The set of all points z with the described property is called the kernel of P.
Contents |
[edit] 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.
[edit] 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.
[edit] 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[1]. Lee and Preparata[2] presented an algorithm to construct the intersection of interior half-planes in optimal Θ(N) time.
[edit] See also
[edit] References
- ^ a b 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; Russian translation, 1989: ISBN 5-03-001041-6.
- ^ 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
