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" }```