## 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