Well-separated pair decomposition for the unitdisk graph metric and its applications

We extend the classic notion of well-separated pair decom-position [10] to the (weighted) unit-disk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. We show that for the unit-disk graph metric of n points in the plane and for any constant c ≥ 1, there exists a c-well-separated pair decomposition with O(n log n) pairs, and the decomposition can be computed in O(n log n) time. We also show that for the unit-ball graph metric in k dimensions where k ≥ 3, there exists a c-well-separated pair decomposition with O(n2−2/k) pairs, and the bound is tight in the worst case. We present the application of the well-separated pair decomposition in obtaining efficient algo-rithms for approximating the diameter, closest pair, nearest neighbor, center, median, and stretch factor, all under the unit-disk graph metric. Categories and Subject Descriptors E.1 [Data]: data structures—graphs and networks; F.2.2 [Theory of Computation]: analysis of algorithms and problem complexity—non-numerical algorithms and prob-lems; G.2.2 [Discrete Mathematics]: graph theory—graph algorithm