TY - GEN
T1 - Approximate shortest paths and distance oracles in weighted unit-disk graphs
AU - Chan, Timothy M.
AU - Skrepetos, Dimitrios
N1 - Publisher Copyright:
© Timothy M. Chan and Dimitrios Skrepetos; licensed under Creative Commons License CC-BY 34th Symposium on Computational Geometry (SoCG 2018).
PY - 2018/6/1
Y1 - 2018/6/1
N2 - We present the first near-linear-time (1 + ϵ)-approximation algorithm for the diameter of a weighted unit-disk graph of n vertices, running in O (nlog2 n) time, for any constant ϵ > 0, improving the near-O n3/2)-time algorithm of Gao and Zhang [STOC 2003]. Using similar ideas, we can construct a (1 + ϵ)-approximate distance oracle for weighted unit-disk graphs with O(1) query time, with a similar improvement in the preprocessing time, from near O(n3/2) to O (n log3 n). We also obtain new results for a number of other related problems in the weighted unit-disk graph metric, such as the radius and bichromatic closest pair. As a further application, we use our new distance oracle, along with additional ideas, to solve the (1 + ϵ)-approximate all-pairs bounded-leg shortest paths problem for a set of n planar points, with near O (n2.579) preprocessing time, O (n2logn) space, and O (loglogn) query time, improving thus the near-cubic preprocessing bound by Roditty and Segal [SODA 2007].
AB - We present the first near-linear-time (1 + ϵ)-approximation algorithm for the diameter of a weighted unit-disk graph of n vertices, running in O (nlog2 n) time, for any constant ϵ > 0, improving the near-O n3/2)-time algorithm of Gao and Zhang [STOC 2003]. Using similar ideas, we can construct a (1 + ϵ)-approximate distance oracle for weighted unit-disk graphs with O(1) query time, with a similar improvement in the preprocessing time, from near O(n3/2) to O (n log3 n). We also obtain new results for a number of other related problems in the weighted unit-disk graph metric, such as the radius and bichromatic closest pair. As a further application, we use our new distance oracle, along with additional ideas, to solve the (1 + ϵ)-approximate all-pairs bounded-leg shortest paths problem for a set of n planar points, with near O (n2.579) preprocessing time, O (n2logn) space, and O (loglogn) query time, improving thus the near-cubic preprocessing bound by Roditty and Segal [SODA 2007].
KW - Distance oracles
KW - Planar graphs
KW - Shortest paths
KW - Unit-disk graphs
UR - http://www.scopus.com/inward/record.url?scp=85048967994&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048967994&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2018.24
DO - 10.4230/LIPIcs.SoCG.2018.24
M3 - Conference contribution
AN - SCOPUS:85048967994
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 241
EP - 2413
BT - 34th International Symposium on Computational Geometry, SoCG 2018
A2 - Toth, Csaba D.
A2 - Speckmann, Bettina
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th International Symposium on Computational Geometry, SoCG 2018
Y2 - 11 June 2018 through 14 June 2018
ER -