DIMACS TR: 93-57

Finding a Shortest Diagonal of a Simple Polygon in Linear Time



Authors: John Hershberger and Subhash Suri

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 \Omega(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.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-57.ps
DIMACS Home Page