DIMACS TR: 93-58

Matrix Searching with the Shortest Path Metric

Authors: John Hershberger and Subhash Suri


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