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