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

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 log² n) time for any constant ε > 0, so we considerably improve upon the near-O (n^3/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 (n^3/2) to O (n log³ 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 (n² log n) space, O (log log n) query time, and nearly O (n^2: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].