
J. Gao and L. Zhang, WellSeparated Pair Decomposition for the UnitDisk Graph Metric and its Applications, Proc. the 35th ACM Symposium on Theory of Computing (STOC'03), 483492, June, 2003.
Abstract:
We extend the classic notion of wellseparated pair decomposition~\cits{ckdmpsa95} to the (weighted) unitdisk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. We show that for the unitdisk graph metric of $n$ points in the plane and for any constant $c\geq 1$, there exists a $c$wellseparated 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 unitball graph metric in $k$ dimensions where $k\geq 3$, there exists a $c$wellseparated pair decomposition with $O(n^{22/k})$ pairs, and the bound is tight in the worst case. We present the application of the wellseparated pair decomposition in obtaining efficient algorithms for approximating the diameter, closest pair, nearest neighbor, center, median, and stretch factor, all under the unitdisk graph metric.
Bibtex:
@inproceedings{gzwspdu03,
author="Jie Gao and Li Zhang",
title="WellSeparated Pair Decomposition for the UnitDisk Graph Metric and its Applications",
booktitle="Proc. the 35th ACM Symposium on Theory of Computing (STOC'03)",
pages="483492",
month="June",
year="2003"
}

