Computing the L-1 Geodesic Diameter and Center of a Polygonal DomainShow others and affiliations
2017 (English)In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 57, no 3, p. 674-701Article in journal (Refereed) Published
Abstract [en]
For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the geodesic diameter in time and the geodesic center in time, respectively, 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 or time, and compute the geodesic center in time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on shortest paths in polygonal domains.
Place, publisher, year, edition, pages
SPRINGER , 2017. Vol. 57, no 3, p. 674-701
Keywords [en]
Geodesic diameter; Geodesic center; Shortest paths; Polygonal domains; L-1 metric
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-136571DOI: 10.1007/s00454-016-9841-zISI: 000395193000009OAI: oai:DiVA.org:liu-136571DiVA, id: diva2:1090307
Note
Funding Agencies|Basic Science Research Program through the National Research Foundation of Korea (NRF) - Ministry of Science, ICT & Future Planning [2013R1A1A1A05006927]; Ministry of Education [2015R1D1A1A01057220]; JSPS/MEXT [12H00855, 15H02665, JP24106005, JP24700008, JP24220003, JP15K00009]; MEXT KAKENHI [24106008]; US-Israel Binational Science Foundation [2010074]; National Science Foundation [CCF-1018388, CCF-1526406, CCF-1317143]; JST, CREST, Foundation of Innovative Algorithms for Big Data; Swedens innovation agency VINNOVA [2014-03476]; Swedish Transport Administration Trafikverket
2017-04-242017-04-242017-04-24