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 . 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 .
ASJC Scopus subject areas
- Geometry and Topology
- Computer Science Applications
- Computational Theory and Mathematics