Matrix searching with the shortest-path metric

We present an O(n) time algorithm for computing row-wise maxima or minima of an implicit, totally monotone n x n 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.