TY - GEN

T1 - Approximate shortest paths and distance oracles in weighted unit-disk graphs

AU - Chan, Timothy M.

AU - Skrepetos, Dimitrios

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 -