## DIMACS TR: 93-58

## Matrix Searching with the Shortest Path Metric

### Authors: John Hershberger and Subhash Suri

**
ABSTRACT
**

We present an O(n) time algorithm for computing row-wise maxima or
minima of an implicit, totally-monotone nxn matrix whose entries
represent shortest-path distances between pairs of vertices in a
simple polygon. We apply this result to derive improved algorithms
for several well-known problems in computational geometry. Most
prominently, we obtain linear-time algorithms for computing the
geodesic diameter, all farthest neighbors, and external farthest
neighbors of a simple polygon, improving the previous best result
by a factor of O(log n) in each case.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-58.ps

DIMACS Home Page