An Optimal Algorithm for Finding the Kernel of a Polygon.
ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB
Pagination or Media Count:
The kernel KP 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, KP is the intersection of appropriate half-planes determined by the polygons edges. Although the intersection of n generic half-planes is known to require time 0n log n, we show that one can exploit the ordering of the half-planes corresponding to the sequence of the polygons edges to obtain a kernel finding algorithm which runs in time 0n and is therefore optimal. Author
- Theoretical Mathematics