language: en

Finding a Shortest Diagonal of a Simple Polygon in Linear Time

John Hershberger
DEC/SRC
130 Lytton Avenue, Palo Alto, California 94301
Subhash Suri
Bellcore
445 South Street, Morristown, New Jersey 07960
August 16, 1993

Abstract A diagonal of a planar, simple polygon P is an open line segment that connects two non-adjacent vertices and lies in the relative interior of P . We present a linear time algorithm for finding a shortest diagonal (in the L 2 norm) of a simple polygon, improving the previous best result by a factor of log n. Our result provides an interesting contrast to a known (n log n) lower bound for finding a closest pair of vertices in a simple polygon|observe that a shortest diagonal is defined by a closest pair of vertices satisfying an additional visibility constraint.