Accession Number:

ADA056887

Title:

An Optimal Algorithm for Finding the Kernel of a Polygon.

Descriptive Note:

Technical rept.,

Corporate Author:

ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB

Personal Author(s):

• Lee,D. T.
• Preparata,F. P.

Report Date:

1977-07-01

Pagination or Media Count:

12.0

Abstract:

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

Descriptors:

• *ALGORITHMS
• PROBLEM SOLVING
• KERNEL FUNCTIONS
• GEOMETRY
• POLYGONS
• CONVEX SETS

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE