WorksComputer Science
A Linear-Size Well-Separated Pair Decomposition for Unit Disk Graphs
Abstract
Given a metric space a -well separated pair decomposition (WSPD) is a collection of `dumbbell' pairs of subsets , , where the distance between the two sets is at least times the diameter of each set and every pair of points in is covered by one such pair. It is known that for a weighted unit disk graph metric of points, there is a WSPD of size . But it is open whether this bound can be improved to . In this note, we answer this question affirmatively and provide an algorithm that yields a linear-size WSPD for unit disk graphs.
Introduction
Given a metric , a pair of subsets with , is called a -well-separated pair, , if the distance between them is at least times the diameter of each pair. Here, we use to refer to the distance between two sets , , and as the diameter of a set , . Now, a -well-separated pair decomposition (-WSPD) is a set of -well-separated pairs that cover every pair of points in . That is, , such that and or vice versa, and ,
We consider the metric to be the shortest-path metric of a weighted unit disk graph. In particular, consider to be a set of points in . An edge connects two points if their Euclidean distance is at most 1. The edge is also given a weight equal to the Euclidean distance. The metric measures the shortest path distance between two points in this graph . It is shown in [8] that for any there is a -well separated pair decomposition of the unit disk graph metric of size when , and of size when . The size of the WSPD for dimension 3 or higher is tight – there is an example where any -WSPD has to be of size . But it has been open since [8]1 whether one can find a linear-size WSPD for the unit disk graph in 2D, or if one can show a stronger lower bound of .
New Results. In this note, we present a new algorithm that produces a -WSPD for any of size , settling this question. The main result is the following theorem.
Theorem 1.1. For a unit disk graph of points in the plane, there is a -well-separated pair decomposition of size for any .
In this document, we first show that the algorithm in [8] may produce a WSPD of size . Thus, the analysis of the algorithm in [8] is actually tight in terms of . The algorithm in [8] takes a bounded-degree spanning tree and recursively performs a balanced partitioning. It turns out if the tree is not carefully chosen, the subtrees or clusters in this hierarchical decomposition may be very close to each other, generating a super-linear number of well-separated pairs.
The improvement to a linear-size WSPD uses a hierarchical net-tree, where the centers at level are required to be at distance at least apart. To bound the total size, the analysis uses a randomized padded decomposition [KPR93] and a potential function argument to balance the number of pairs across different levels. Note that the padded decomposition is used only for the analysis and the algorithm uses a deterministic net-tree. The running time of the new algorithm is , dominated by the time to find all-pairs shortest paths of a unit disk graph [2]. Note that the algorithm by Gao and Zhang [8] has running time , as it does not require finding the all-pairs shortest path distances. Instead, it uses the Euclidean distance as a lower bound of the graph distance and the number of points minus one as an upper bound on the diameter of a connected subgraph.
Last, we note that Har-Peled et. al. [10] had an output-sensitive algorithm for WSPD of a given metric. If a metric admits an WSPD, the algorithm will be able to find one. Thus, applying Har-Peled’s algorithm to the unit disk graph metric would also produce a linear-size WSPD – since we now know its existence.
Related Work. Well-separated pair decomposition was initially proposed for points in by Callahan and Kosaraju [3] – any points in admits a -WSPD of size . Later, it is shown that a linear-size WSPD exists for metrics of bounded doubling dimension [9]. A unit disk graph metric does not have bounded doubling dimension. A -WSPD of size is shown for a -low-density graph [7]. And a linear-size WSPD is shown for -packed graphs [4]. Finally, Buchin et. al. [1] considered the problem of minimizing the size of a WSPD for a given input point set.
AI Disclosure. The main technique idea – the potential function in the proof – was discovered by ChatGPT Astra. This note is entirely written by the author.
Size for the Gao-Zhang Algorithm
We briefly review the algorithm in [8]. In this discussion, we only consider a point set of constant density – the maximum number of points inside a unit disk is . To build a WSPD, we first construct a spanning tree of the unit disk graph of maximum degree at most 6 and then recursively build a balanced decomposition – on a tree of maximum degree at most , there is an edge whose removal partitions the tree into two parts of size at least a fraction of . The decomposition can be represented by a binary tree in which the root represents the entire tree and the two children represent the connected subtrees obtained by removing an edge from . Each node in the tree represents a connected subtree of . Denote by the set of vertices in . One vertex of is chosen as the representative of .
The algorithm for constructing a -WSPD in [8] is as follows. Start with a pair in a queue, where is the root of , and thus is the set of all points in . Proceed until the queue is empty. In each step, remove the first pair from the queue and consider the following cases:
If , insert the pair to the well separated pair decomposition. Here is the Euclidean distance between and .
Otherwise, if , they contain the same point and we discard the pair. Without loss of generality let’s assume and that are two children of , we add to the queue two pairs and .
We show that the algorithm on the following example produces pairs. Consider as a power of 2 and a unit disk graph as a unit grid of . All the edges are precisely the grid edges. We also consider a spanning tree as a path that zigzags from the bottom up. See Figure 1. The hierarchical decomposition of the tree iteratively bisects the path. Take .
Figure 1. A WSPD of size by the algorithm in [8].
We first argue that any well-separated pair produced by the algorithm in [8] cannot have a set of diameter greater than . Indeed, the graph diameter is . By the design of the hierarchical partition, each well-separated pair produced by the algorithm must have all vertices in (and in ) in the same row.
Now consider two points of coordinate and with , and . Suppose they are covered by a -well-separated pair and the representative points in the two sets and are and , respectively. Now we know by construction,
and
Take , we have . Thus, fix and , for all pairs and on the two rows, we need at least well-separated pairs to cover them. There are pairs of rows that are exactly vertically apart. Thus, the number of well-separated pairs is at least
Linear-Size WSPD
We first assume that the points have bounded density; as in [8], the algorithm can be extended to the general case. To get the linear size, we will need a different algorithm. In particular, we build a hierarchical decomposition using a graph-metric net-hierarchy. In this section, we will first present the algorithm and then bound the size of the WSPD.
Algorithm
Consider a unit disk graph with bounded density. We build a nested net hierarchy at scales for integers . At level define a set with all the points. Now we build in a greedy manner. Initialize . Scan the points in . If a point is within distance from an already selected point in , assign ’s parent as . Break ties arbitrarily. If not, add to . The points in have pairwise graph distance at least , and every point in is within distance from at least one point in . The net hierarchy has at most levels.
We define the cluster for a point as the descendants in the hierarchy. The clusters of points in partition . The clusters of different scales are nested. The cluster of a point is a subset of the cluster of the parent of . Any point in a cluster with is at distance at most from . Thus, the graph diameter of a cluster is at most .
Now we use the net-hierarchy to build a -WSPD. We have two procedures: Within builds the well-separated pairs covering pairs within , and Between, for , builds the well-separated pairs covering pairs with one from and the other one from . We start with Within, where is the root of the net-hierarchy.
The procedure Within will quit if is a singleton cluster. Otherwise, we recursively call Within for each child of , and call Between for each unordered pair of children of .
In the procedure Between, if and are singletons, or if , we add the pair to the output WSPD. Otherwise, we call Between for each child of and each child of .
To see why the produced pairs are -well-separated, recall that any point in a cluster (or ) is within distance from (or ), with . By the triangle inequality,
The coverage of the produced well-separated pairs is immediate.
To implement the algorithm, we first run all-pairs shortest paths for the unit disk graph in time [2]. The recursive call takes time at most .
Size of WSPD
We now bound the size of the WSPD by the above algorithm. The main Lemma we prove is the following.
Lemma 3.1. For a weighted unit disk graph with bounded density, at scale , let be any set of vertices that are pairwise more than -apart and for a constant , then , for a sufficiently large constant .
This Lemma is enough to prove our main claim. In particular, every well-separated pair we produced at each level is charged to some pair of points . By the recursive algorithm, their parents either collide () or fail to be well-separated at level , in which case, . Thus
Thus, each well-separated pair generated by the algorithm can be charged to a pair in in Lemma 3.1. The total number of well-separated pairs produced at level at most for a constant is by the bounded density assumption.
The proof of this lemma requires the use of padded decomposition of weighted planar graphs. In particular, a weighted unit-disk graph has a planar spanner of constant stretch [6]. That is, there is a subgraph of the weighted unit disk graph such that , for a constant . Here refers to the shortest path distance in graph .
Now consider the planar graph , by [KPR93], there is an absolute constant such that, for every , there is a random partition of satisfying for every cluster , and for any and ,
Here denotes the cluster containing and the set of points within distance from in graph .
By the spanner property, we have . Also . Therefore, the partition of satisfies and for any and ,
We will skip the subscript from now on, and all distances and diameter are in the graph . Now, we are ready to prove the Lemma.
Proof. We build a nested padded hierarchy on a unit disk graph . For each , we independently sample a partition with . .
For any , denote by the cluster in that contains vertex . Define the common intersection . If has multiple connected components, split the components into their own clusters. This provides a nested partition . . These partitions have the following property: each cluster is connected and has diameter at most ; refines – one cluster in is decomposed into several clusters in ; each cluster in is in a cluster of .
Last, a ball induces a connected subgraph. Consequently, if the ball is contained in every , , then it is contained in the connected component . By a union bound, we have
For the setup of the Lemma, we will relate the pairs in to the partition . Consider a pair in . Call the pair good if all three events hold:
By Equation (1), the first two events fail with probability at most , and the third fails with probability at most . By the union bound, the probability that is good is at least . Let be the expected number of good pairs at level . . In the following, we will bound to be . This will be enough for the lemma.
A good pair has the following property. Since and the ball at of radius stays in a cluster , both stay in this cluster. Further, and clusters in have diameter at most ; and stay in different clusters in . Last, since the ball at of radius stays in cluster , the cluster has diameter at least , if . To see why, follow the shortest path from to and stop at the last vertex right before exceeding distance from ; stays in the cluster . Since the diameter of the cluster is at least , it has at least vertices.
Now fix a cluster . Let be all the descendant clusters of in and let be the number of these clusters with diameter at least . The number of good pairs that can be generated from the clusters is at most . To bound this value, we use a potential function argument.
For any connected vertex set , we define a potential function
Since is connected and each edge has weight at most , . Thus . Now suppose a cluster is partitioned into connected pieces . Consider the increase of the potential function
Recall that and are all connected subgraphs. If we shrink to a supernode, the subgraph on has diameter at most . Thus . This means,
The increase of the potential function provides an upper bound on . Further, if we count all good pairs with different values of , the sum of the differences of the potential function allows telescoping, which provides the final bound. We explain the details next.
Now we are ready to bound the value . Apply Equation (2) for our case of and its decomposition into . we have
Now we do a case study of . If , by Equation (4) we have . Or, . Since the point set has bounded density and has radius at most , we have for some constant . has subsets, each of at least vertices. Thus . Combining the two inequalities, we have . Altogether, we have
If , apply Equation (3), we have
Therefore, in both cases, we have for a constant .
To bound the total number of good pairs at level , , we now sum over all clusters in level . Define .
Now,
Recall that the sum of the potential function increases as the level goes up. . and . Thus,
This finishes the Lemma.
To complete Theorem 1.1, we use the same idea as in Section 4.2 of [8] to handle a general set of points, thus dropping the bounded density assumption.
References
- [1]Kevin Buchin, Jacobus Conradi, Sariel Har-Peled, Antonia Kalb, Abhiruk Lahiri, Lukas Plätz, Carolin Rehs, and Sampson Wong. On Small Pair Decompositions for Point Sets. In Philip Bille, Seth Pettie, and Sabine Storandt, editors, 34th Annual European Symposium on Algorithms (ESA 2026), volume 388 of Leibniz International Proceedings in Informatics (LIPIcs), pages 102:1–102:22, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.102, doi:10.4230/LIPIcs.ESA.2026.102.DOI
- [2]Bruce W. Brewer and Haitao Wang. An improved algorithm for shortest paths in weighted unit-disk graphs. Computing in Geometry and Topology, 5(2):2:1–2:14, 2026. doi:10.57717/cgt.v5i2.69.
- [3]Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM, 42(1):67–90, 1995. doi:10.1145/200836.200853.DOI
- [4]Lindsey Deryckere, Joachim Gudmundsson, André van Renssen, Yuan Sha, and Sampson Wong. A WSPD, separator and small tree cover for c-packed graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025), volume 349 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.21, doi:10.4230/LIPIcs.WADS.2025.21.DOI
- [5]Arnold Filtser. On strong diameter padded decompositions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:21, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.6, doi: 10.4230/LIPIcs.APPROX-RANDOM.2019.6.
- [6]Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, and An Zhu. Geometric spanner for routing in mobile networks. In Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc), pages 45–55, 2001. doi:10.1145/501422.501424.DOI
- [7]Joachim Gudmundsson and Sampson Wong. A well-separated pair decomposition for low density graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page ..., 2026. URL: https://arxiv.org/abs/2411.08204, doi: 10.48550/arXiv.2411.08204.
- [8]Jie Gao and Li Zhang. Well-separated pair decomposition for the unit-disk graph metric and its applications. In Proc. the 35th ACM Symposium on Theory of Computing (STOC’03), pages 483–492, June 2003.
- [9]Sariel Har-Peled and Manor Mendel. Fast construction of nets in low-dimensional metrics, and their applications. SIAM Journal on Computing, 35(5):1148–1184, 2006. doi:10.1137/S0097539704446281.
- [10]Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson. Well-separated pairs decomposition revisited, 2025. URL: https://arxiv.org/abs/2509.05997, arXiv: 2509.05997.
