Computing the L-1 Geodesic Diameter and Center of a Polygonal Domain
2017
Online
Elektronische Ressource
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.
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
Titel: |
Computing the L-1 Geodesic Diameter and Center of a Polygonal Domain
|
---|---|
Link: | |
Veröffentlichung: | 2017 |
Medientyp: | Elektronische Ressource |
DOI: | 10.1007.s00454-016-9841-z |
Schlagwort: |
|
Sonstiges: |
|