The all-geodesic furthest neighbor problem for simple polygons
Subhash Suri · 1987
We present an O(n logn) time and O (n) space algorithm for the following problem in a simple polygon P with n vertices: For each vertex u of P, find another vertex p(u) that is furthest from u, where the distance between two points is measured by the length of the shortest internal path connecting them in P. As a corollary, the longest internal path in P, called the geodesic diameter, also can be found within the same time and space bound. All the previously known algorithms for computing the geodesic diameter have required O(n2) time in the worst case, e.g. see Chazelle [5], Reif and Storer [16] and Toussaint [19].