2026-08-01T09:11:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5715 2024-03-06T10:36:54Z ddc:004 open_access

Computing the L1 Geodesic Diameter and Center of a Polygonal Domain Won Bae, Sang Korman, Matias Mitchell, Joseph S. B. Okamoto, Yoshio Polishchuk, Valentin Wang, Haitao geodesic diameter geodesic center shortest paths polygonal domains L1 metric 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, where alpha(.) 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^{12+epsilon}) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L_1 shortest paths in polygonal domains. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sang Won Bae and Matias Korman and Joseph S. B. Mitchell and Yoshio Okamoto and Valentin Polishchuk and Haitao Wang 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.14 urn:nbn:de:0030-drops-57151 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.14 eng https://creativecommons.org/licenses/by/3.0/legalcode