Computing the $$L_1$$ Geodesic Diameter and Center of a Polygonal Domain.

For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the $$L_1$$ geodesic diameter in $$O(n^2+h^4)$$ time and the $$L_1$$ geodesic center in $$O((n^4+n^2 h^4)\alpha (n))$$ time, respectively, where $$\alpha (\cdot )$$ denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in $$O(n^{7.73})$$ or $$O(n^7(h+\log n))$$ time, and compute the geodesic center in $$O(n^{11}\log n)$$ time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on $$L_1$$ shortest paths in polygonal domains. [ABSTRACT FROM AUTHOR]