The Well-Separated Pair Decomposition

for the Unit-Disk Graph Metric

for the Unit-Disk Graph Metric

I will present the following result of Gao and Zhang (SICOMP 2005): Let $S$ be a set of $n$ points in the plane, and consider the metric space in which the distance between two points is their shortest-path distance in the unit-disk graph. In $O(n \log n)$ time, we can compute a well-separated pair decomposition for this metric space, consisting of $O(n \log n)$ pairs.