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