TY - GEN
T1 - Computing the L1 geodesic diameter and center of a polygonal domain
AU - Bae, Sang Won
AU - Korman, Matias
AU - Mitchell, Joseph S.B.
AU - Okamoto, Yoshio
AU - Polishchuk, Valentin
AU - Wang, Haitao
N1 - Funding Information:
Work by S. W. Bae was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (2013R1A1A1A05006927), and by the Ministry of Education (2015R1D1A1A01057220). M. Korman was supported in part by the ELC project (MEXT KAKENHI No. 24106008). J. Mitchell acknowledges support from the US-Israel Binational Science Foundation (grant 2010074) and the National Science Foundation (CCF-1018388, CCF-1526406). Y. Okamoto is partially supported by Grant-in-Aid for Scientific Research (KAKENHI) 24106005, 24700008, 24220003, 15K00009. V. Polishchuk is supported in part by Grant 2014-03476 from the Sweden''s innovation agency VINNOVA. H. Wang was supported in part by the National Science Foundation (CCF-1317143).
Publisher Copyright:
© Sang W. Bae, Matias Korman, Joseph Mitchell, Yoshio Okamoto, Valentin Polishchuk, and Haitao Wang; licensed under Creative Commons License CC-BY.
PY - 2016/2/1
Y1 - 2016/2/1
N2 - 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.
AB - 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.
KW - Geodesic center
KW - Geodesic diameter
KW - L metric
KW - Polygonal domains
KW - Shortest paths
UR - http://www.scopus.com/inward/record.url?scp=84961589887&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84961589887&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2016.14
DO - 10.4230/LIPIcs.STACS.2016.14
M3 - Conference contribution
AN - SCOPUS:84961589887
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016
A2 - Vollmer, Heribert
A2 - Ollinger, Nicolas
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016
Y2 - 17 February 2016 through 20 February 2016
ER -