@inproceedings{21f3345812394731be6c911ca5171d1b,
title = "Computing the L1 geodesic diameter and center of a polygonal domain",
abstract = "For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L1 geodesic diameter in O(n2+h4) time and the L1 geodesic center in O((n4+n2h4)α(n)) time, where α(·) 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(n7.73) or O(n7(h+log n)) time, and compute the geodesic center in O(n12+∈) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L1 shortest paths in polygonal domains.",
keywords = "Geodesic center, Geodesic diameter, L metric, Polygonal domains, Shortest paths",
author = "Bae, \{Sang Won\} and Matias Korman and Mitchell, \{Joseph S.B.\} and Yoshio Okamoto and Valentin Polishchuk and Haitao Wang",
note = "Publisher Copyright: {\textcopyright} Sang W. Bae, Matias Korman, Joseph Mitchell, Yoshio Okamoto, Valentin Polishchuk, and Haitao Wang; licensed under Creative Commons License CC-BY.; 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 ; Conference date: 17-02-2016 Through 20-02-2016",
year = "2016",
month = feb,
day = "1",
doi = "10.4230/LIPIcs.STACS.2016.14",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Heribert Vollmer and Nicolas Ollinger",
booktitle = "33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016",
}