Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.14
URN: urn:nbn:de:0030-drops-57151
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5715/
Won Bae, Sang ; Korman, Matias ; Mitchell, Joseph S. B. ; Okamoto, Yoshio ; Polishchuk, Valentin ; Wang, Haitao
Computing the L1 Geodesic Diameter and Center of a Polygonal Domain
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{wonbae_et_al:LIPIcs:2016:5715,
author = {Sang Won Bae and Matias Korman and Joseph S. B. Mitchell and Yoshio Okamoto and Valentin Polishchuk and Haitao Wang},
title = {{Computing the L1 Geodesic Diameter and Center of a Polygonal Domain}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {14:1--14:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-001-9},
ISSN = {1868-8969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5715},
URN = {urn:nbn:de:0030-drops-57151},
doi = {10.4230/LIPIcs.STACS.2016.14},
annote = {Keywords: geodesic diameter, geodesic center, shortest paths, polygonal domains, L1 metric}
}
| Keywords: | geodesic diameter, geodesic center, shortest paths, polygonal domains, L1 metric | |
| Seminar: | 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 16.02.2016 |
