TY - JOUR
T1 - Approximate shortest paths and distance oracles in weighted unit-disk graphs
AU - Chan, Timothy M.
AU - Skrepetos, Dimitrios
N1 - Publisher Copyright:
© 2019, (publisher Name). All rights reserved.
PY - 2019
Y1 - 2019
N2 - We present the first near-linear-time algorithm that computes a (1 + ε)- approximation of the diameter of a weighted unit-disk graph of n vertices. Our algorithm requires O (n log2 n) time for any constant ε > 0, so we considerably improve upon the near-O (n3/2) -time algorithm of Gao and Zhang [17]. Using similar ideas we develop (1+ε)- approximate distance oracles of O (1) query time with a likewise improvement in the preprocessing time, specifically from near O (n3/2) to O (n log3 n). We also obtain similar new results for a number of related problems in the weighted unit-disk graph metric such as the radius and the bichromatic closest pair. As a further application we employ our distance oracle, along with additional ideas, to solve the (1 + ε)-approximate all-pairs bounded-leg shortest paths (apBLSP) problem for a set of n planar points. Our data structure requires O (n2 log n) space, O (log log n) query time, and nearly O (n2:579) preprocessing time for any constant ε > 0, and is the first that breaks the near-cubic preprocessing time bound given by Roditty and Segal [31].
AB - We present the first near-linear-time algorithm that computes a (1 + ε)- approximation of the diameter of a weighted unit-disk graph of n vertices. Our algorithm requires O (n log2 n) time for any constant ε > 0, so we considerably improve upon the near-O (n3/2) -time algorithm of Gao and Zhang [17]. Using similar ideas we develop (1+ε)- approximate distance oracles of O (1) query time with a likewise improvement in the preprocessing time, specifically from near O (n3/2) to O (n log3 n). We also obtain similar new results for a number of related problems in the weighted unit-disk graph metric such as the radius and the bichromatic closest pair. As a further application we employ our distance oracle, along with additional ideas, to solve the (1 + ε)-approximate all-pairs bounded-leg shortest paths (apBLSP) problem for a set of n planar points. Our data structure requires O (n2 log n) space, O (log log n) query time, and nearly O (n2:579) preprocessing time for any constant ε > 0, and is the first that breaks the near-cubic preprocessing time bound given by Roditty and Segal [31].
UR - http://www.scopus.com/inward/record.url?scp=85066748410&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85066748410&partnerID=8YFLogxK
U2 - 10.20382/jocg.v10i2
DO - 10.20382/jocg.v10i2
M3 - Article
AN - SCOPUS:85066748410
SN - 1920-180X
VL - 10
SP - 3
EP - 20
JO - Journal of Computational Geometry
JF - Journal of Computational Geometry
IS - 2
ER -