J. Gao and L. Zhang, Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and its Applications, Proc. the 35th ACM Symposium on Theory of Computing (STOC'03), 483-492, June, 2003.

Abstract:

We extend the classic notion of well-separated pair decomposition~\cits{ck-dmpsa-95} 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\geq 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\geq 3$, there exists a $c$-well-separated pair decomposition with $O(n^{2-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 algorithms for approximating the diameter, closest pair, nearest neighbor, center, median, and stretch factor, all under the unit-disk graph metric.

Bibtex: 

@inproceedings{gz-wspdu-03,
      author="Jie Gao and Li Zhang", 
      title="Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and its Applications", 
      booktitle="Proc. the 35th ACM Symposium on Theory of Computing (STOC'03)", 
      pages="483--492", 
      month="June", 
      year="2003"
}