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

Sang Won Bae, Matias Korman, Joseph S. B. Mitchell +3

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…