MATRIX SEARCHING WITH THE SHORTEST-PATH METRIC

We present an O(n) time algorithm for computing row-wise maxima or min ima of an implicit, totally monotone n x n matrix whose entries repres ent shortest-path distances between pairs of vertices in a simple poly gon. We apply this result to derive improved algorithms for several we ll-known problems in computational geometry. Most prominently, we obta in linear-time algorithms for computing the geodesic diameter, all far thest neighbors, and external farthest neighbors of a simple polygon, improving the previous best result by a factor of O(log n) in each cas e.