Computing the $ L_1 $ Geodesic Diameter and Center of a Polygonal Domain
2016 (English)In: Leibniz International Proceedings in Informatics, ISSN 1868-8969, E-ISSN 1868-8969, Vol. 47, 14:1-14:14 p.Article in journal (Refereed) PublishedText
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.
Place, publisher, year, edition, pages
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik , 2016. Vol. 47, 14:1-14:14 p.
geodesic diameter, geodesic center, shortest paths, polygonal domains, L1 metric
Computer Science Medical Image Processing
IdentifiersURN: urn:nbn:se:liu:diva-128031DOI: 10.4230/LIPIcs.STACS.2016.14OAI: oai:DiVA.org:liu-128031DiVA: diva2:928732