An Optimal Algorithm for Finding the Kernel of a Polygon.
Abstract
The kernel K(P) of a simple polygon P with n vertices is the locus of the points internal to P from which all vertices of P are visible. Equivalently, K(P) is the intersection of appropriate half-planes determined by the polygon's edges. Although the intersection of n generic half-planes is known to require time 0(n log n), we show that one can exploit the ordering of the half-planes corresponding to the sequence of the polygon's edges to obtain a kernel finding algorithm which runs in time 0(n) and is therefore optimal. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1977
- Accession Number
- ADA056887
Entities
People
- D. T. Lee
- Franco P. Preparata
Organizations
- University of Illinois Urbana–Champaign