betaFeedback

WorksComputer Science

A Linear-Size Well-Separated Pair Decomposition for Unit Disk Graphs

Abstract

Given a metric space (X,d)(X, d) a cc-well separated pair decomposition (WSPD) is a collection of `dumbbell' pairs of subsets (A,B)(A, B), A,B⊆XA, B\subseteq X, where the distance between the two sets is at least cc times the diameter of each set and every pair of points in XX is covered by one such pair. It is known that for a weighted unit disk graph metric of nn points, there is a WSPD of size O(nlog⁡n)O(n\log n). But it is open whether this bound can be improved to O(n)O(n). 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 (X,d)(X,d), a pair of subsets (A,B)(A,B) with A⊆XA \subseteq X, B⊆XB \subseteq X is called a cc-well-separated pair, c>1c>1, if the distance between them is at least cc times the diameter of each pair. Here, we use d(A,B)d(A,B) to refer to the distance between two sets A,B⊆XA,B \subseteq X, d(A,B)=min⁡a∈A,b∈Bπ(a,b)d(A,B)=\min_{a\in A,b\in B}\pi(a,b), and D(A)D(A) as the diameter of a set A⊆XA \subseteq X, D(A)=max⁡a∈A,a′∈Ad(a,a′)D(A)=\max_{a\in A,a'\in A}d(a,a'). Now, a cc-well-separated pair decomposition (cc-WSPD) is a set of cc-well-separated pairs P={(Ai,Bi)}\mathcal{P}=\{(A_i,B_i)\} that cover every pair of points in XX. That is, ∀p≠q∈X\forall p\ne q\in X, ∃(Ai,Bi)∈P\exists(A_i,B_i)\in\mathcal{P} such that p∈Aip\in A_i and q∈Biq\in B_i or vice versa, and ∀(Ai,Bi)∈P\forall(A_i,B_i)\in\mathcal{P},

d(Ai,Bi)≥c⋅max⁡{D(Ai),D(Bi)}.d(A_i,B_i)\ge c\cdot\max\{D(A_i),D(B_i)\}.

We consider the metric (X,d)(X,d) to be the shortest-path metric of a weighted unit disk graph. In particular, consider XX to be a set of nn points in Rd\mathbb{R}^d. 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 d(p,q)d(p,q) measures the shortest path distance between two points p,qp,q in this graph GG. It is shown in [8] that for any c>1c>1 there is a cc-well separated pair decomposition of the unit disk graph metric of size O(nlog⁡n)O(n\log n) when d=2d=2, and of size O(n2−2/d)O(n^{2-2/d}) when d≥3d\ge3. The size of the WSPD for dimension 3 or higher is tight – there is an example where any cc-WSPD has to be of size Ω(n2−2/d)\Omega(n^{2-2/d}). 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 Ω(nlog⁡n)\Omega(n\log n).

New Results. In this note, we present a new algorithm that produces a cc-WSPD for any c>1c>1 of size O(n)O(n), settling this question. The main result is the following theorem.

Theorem 1.1. For a unit disk graph of nn points in the plane, there is a cc-well-separated pair decomposition of size O(n)O(n) for any c>1c>1.

In this document, we first show that the algorithm in [8] may produce a WSPD of size Ω(nlog⁡n)\Omega(n\log n). Thus, the analysis of the algorithm in [8] is actually tight in terms of nn. 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 ii are required to be at distance at least 2i2^i 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 O(n2log⁡2n/log⁡log⁡n)O(n^2\log^2 n/\log\log n), 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 O(nlog⁡n)O(n\log n), 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 O(f(n))O(f(n)) 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 Rd\mathbb{R}^d by Callahan and Kosaraju [3] – any nn points in Rd\mathbb{R}^d admits a cc-WSPD of size O(n)O(n). 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 1/ε1/\varepsilon-WSPD of size O(λ2ε−4nlog⁡n)O(\lambda^2\varepsilon^{-4}n\log n) is shown for a λ\lambda-low-density graph [7]. And a linear-size WSPD is shown for cc-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.

Ω(nlog⁡n)\Omega(n\log n) 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 O(1)O(1). To build a WSPD, we first construct a spanning tree TT of the unit disk graph GG of maximum degree at most 6 and then recursively build a balanced decomposition – on a tree of maximum degree at most β\beta, there is an edge whose removal partitions the tree into two parts of size at least a fraction of 1/(β+1)1/(\beta+1). The decomposition can be represented by a binary tree T′T' in which the root represents the entire tree TT and the two children represent the connected subtrees obtained by removing an edge from TT. Each node vv in the tree T′T' represents a connected subtree T(v)T(v) of TT. Denote by S(v)S(v) the set of vertices in T(v)T(v). One vertex of S(v)S(v) is chosen as the representative σ(v)\sigma(v) of T(v)T(v).

The algorithm for constructing a cc-WSPD in [8] is as follows. Start with a pair (S(r),S(r))(S(r),S(r)) in a queue, where rr is the root of T′T', and thus S(r)S(r) is the set of all points in XX. Proceed until the queue is empty. In each step, remove the first pair (S(v1),S(v2))(S(v_1),S(v_2)) from the queue and consider the following cases:

  • If ∥σ(v1)−σ(v2)∥≥(c+2)⋅max⁡(∣S(v1)∣−1,∣S(v2)∣−1)\lVert\sigma(v_1)-\sigma(v_2)\rVert\ge(c+2)\cdot\max\left(|S(v_1)|-1,|S(v_2)|-1\right), insert the pair to the well separated pair decomposition. Here ∥σ(v1)−σ(v2)∥\lVert\sigma(v_1)-\sigma(v_2)\rVert is the Euclidean distance between σ(v1)\sigma(v_1) and σ(v2)\sigma(v_2).

  • Otherwise, if ∣S(v1)∣=∣S(v2)∣=1|S(v_1)|=|S(v_2)|=1, they contain the same point and we discard the pair. Without loss of generality let’s assume ∣S(v1)∣≥∣S(v2)∣|S(v_1)|\ge|S(v_2)| and that u1,u2u_1,u_2 are two children of v1v_1, we add to the queue two pairs (S(u1),S(v2))(S(u_1),S(v_2)) and (S(u2),S(v2))(S(u_2),S(v_2)).

We show that the algorithm on the following example produces Ω(nlog⁡n)\Omega(n\log n) pairs. Consider nn as a power of 2 and a unit disk graph as a unit grid of n×n\sqrt{n}\times\sqrt{n}. All the edges are precisely the grid edges. We also consider a spanning tree TT as a path that zigzags from the bottom up. See Figure 1. The hierarchical decomposition of the tree TT iteratively bisects the path. Take c>2c>2.

Figure 1. A WSPD of size Ω(nlog⁡n)\Omega(n\log n) by the algorithm in [8].

We first argue that any well-separated pair (A,B)(A,B) produced by the algorithm in [8] cannot have a set of diameter greater than n\sqrt{n}. Indeed, the graph diameter is 2n2\sqrt{n}. By the design of the hierarchical partition, each well-separated pair (A,B)(A,B) produced by the algorithm must have all vertices in AA (and in BB) in the same row.

Now consider two points of coordinate (x,y)(x,y) and (x,y+j)(x,y+j) with x∈[n]x\in[\sqrt{n}], j∈[n/2]j\in[\sqrt{n}/2] and 1≤y≤n−j1\le y\le\sqrt{n}-j. Suppose they are covered by a cc-well-separated pair (A,B)(A,B) and the representative points in the two sets AA and BB are σ(A)\sigma(A) and σ(B)\sigma(B), respectively. Now we know by construction,

d(σ(A),σ(B))≥∥σ(A)−σ(B)∥≥(c+2)⋅max⁡(∣A∣−1,∣B∣−1)d(\sigma(A),\sigma(B))\ge\lVert\sigma(A)-\sigma(B)\rVert\ge(c+2)\cdot\max(|A|-1,|B|-1)

and

d(σ(A),σ(B))≤∣A∣−1+j+∣B∣−1d(\sigma(A),\sigma(B))\le|A|-1+j+|B|-1

Take m=max⁡(∣A∣,∣B∣)m=\max(|A|,|B|), we have m≤j/c+1≤2jm\le j/c+1\le2j. Thus, fix yy and jj, for all pairs (x,y)(x,y) and (x,y+j)(x,y+j) on the two rows, we need at least n/(2j)\sqrt{n}/(2j) well-separated pairs to cover them. There are n−j\sqrt{n}-j pairs of rows that are exactly jj vertically apart. Thus, the number of well-separated pairs is at least

∑j=1n/2(n−j)⋅n2j=Ω(nlog⁡n).\sum_{j=1}^{\sqrt{n}/2}(\sqrt{n}-j)\cdot\frac{\sqrt{n}}{2j}=\Omega(n\log n).

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 ri=2ir_i = 2^i for integers i≥0i \ge0. At level −1-1 define a set N−1=XN_{-1} = X with all the points. Now we build Ni⊆Ni−1N_i \subseteq N_{i-1} in a greedy manner. Initialize Ni=∅N_i = \emptyset. Scan the points in Ni−1N_{i-1}. If a point pp is within distance rir_i from an already selected point qq in NiN_i, assign pp’s parent as qq. Break ties arbitrarily. If not, add pp to NiN_i. The points in NiN_i have pairwise graph distance at least rir_i, and every point in Ni−1N_{i-1} is within distance rir_i from at least one point in NiN_i. The net hierarchy has at most J=O(log⁡n)J = O(\log n) levels.

We define the cluster C(p)C(p) for a point p∈Nip \in N_i as the descendants in the hierarchy. The clusters of points in NiN_i partition XX. The clusters of different scales are nested. The cluster of a point p∈Ni−1p \in N_{i-1} is a subset of the cluster of the parent q∈Niq \in N_i of pp. Any point xx in a cluster C(p)C(p) with p∈Nip \in N_i is at distance at most ∑j=0i2j<2i+1=2ri\sum_{j=0}^{i} 2^j < 2^{i+1} = 2r_i from pp. Thus, the graph diameter of a cluster C(p)C(p) is at most 4ri4r_i.

Now we use the net-hierarchy to build a cc-WSPD. We have two procedures: Within(p)(p) builds the well-separated pairs covering pairs within C(p)C(p), and Between(p,q)(p,q), for p,q∈Nip,q \in N_i, builds the well-separated pairs covering pairs with one from C(p)C(p) and the other one from C(q)C(q). We start with Within(r)(r), where rr is the root of the net-hierarchy.

The procedure Within(p)(p) will quit if C(p)={p}C(p) = \{p\} is a singleton cluster. Otherwise, we recursively call Within(q)(q) for each child qq of pp, and call Between(q,w)(q,w) for each unordered pair of children q,wq,w of pp.

In the procedure Between(p,q)(p,q), if C(p)C(p) and C(q)C(q) are singletons, or if d(p,q)≥4(c+1)2id(p,q) \ge4(c+1)2^i, we add the pair (C(p),C(q))(C(p),C(q)) to the output WSPD. Otherwise, we call Between(a,b)(a,b) for each child aa of pp and each child bb of qq.

To see why the produced pairs are cc-well-separated, recall that any point in a cluster C(p)C(p) (or C(q)C(q)) is within distance 2ri2r_i from pp (or qq), with p,q∈Nip,q \in N_i. By the triangle inequality,

d(C(p),C(q))≥d(p,q)−4ri≥c⋅4ri≥c⋅max⁡(D(C(p)),D(C(q))).d(C(p), C(q)) \ge d(p,q) - 4r_i \ge c \cdot4r_i \ge c \cdot\max(D(C(p)), D(C(q))).

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 GG in time O(n2log⁡2n/log⁡log⁡n)O(n^2 \log^2 n/\log\log n) [2]. The recursive call takes time at most O(n2log⁡n)O(n^2 \log n).

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 ri=2ir_i = 2^i, let NiN_i be any set of vertices that are pairwise more than rir_i-apart and Ei={{u,v}⊆Ni:d(u,v)≤Kri}E_i = \{\{u,v\} \subseteq N_i : d(u,v) \le K r_i\} for a constant KK, then ∑i>i0∣Ei∣=O(K2n)\sum_{i>i_0} |E_i| = O(K^2 n), for a sufficiently large constant i0i_0.

This Lemma is enough to prove our main claim. In particular, every well-separated pair we produced at each level ii is charged to some pair of points p,q∈Nip,q \in N_i. By the recursive algorithm, their parents p′,q′∈Ni+1p', q' \in N_{i+1} either collide (p′=q′p' = q') or fail to be well-separated at level i+1i+1, in which case, d(p′,q′)≤4(c+1)2i+1d(p',q') \le4(c+1)2^{i+1}. Thus

d(p,q)≤d(p,p′)+d(p′,q′)+d(q′,q)≤(8c+12)⋅2i.d(p,q) \le d(p,p') + d(p',q') + d(q',q) \le(8c+12)\cdot2^i.

Thus, each well-separated pair generated by the algorithm can be charged to a pair in EiE_i in Lemma 3.1. The total number of well-separated pairs produced at level at most i0i_0 for a constant i0i_0 is O(n)O(n) 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 HH of the weighted unit disk graph GG such that dH(p,q)≤α⋅dG(p,q)d_H(p,q) \le\alpha\cdot d_G(p,q), for a constant α\alpha. Here dHd_H refers to the shortest path distance in graph HH.

Now consider the planar graph HH, by [KPR93], there is an absolute constant b≥1b \ge1 such that, for every Δ>0\Delta> 0, there is a random partition QΔ\mathcal{Q}_{\Delta} of XX satisfying DH(C)≤Δ2D_H(C) \le\Delta^2 for every cluster C∈QΔC \in\mathcal{Q}_{\Delta}, and for any v∈Xv \in X and t≥0t \ge0,

Pr⁡[BH(v,t)⊈QΔ(v)]≤btΔ\Pr[B_H(v,t) \not\subseteq\mathcal{Q}_{\Delta}(v)] \le b\frac{t}{\Delta}

Here QΔ(v)\mathcal{Q}_{\Delta}(v) denotes the cluster containing vv and BH(v,r)B_H(v,r) the set of points within distance rr from vv in graph HH.

By the spanner property, we have BG(v,t)⊆BH(v,αt)B_G(v,t) \subseteq B_H(v,\alpha t). Also DG(C)≤DH(C)≤ΔD_G(C) \le D_H(C) \le\Delta. Therefore, the partition QΔ\mathcal{Q}_{\Delta} of XX satisfies DG(C)≤ΔD_G(C) \le\Delta and for any v∈Xv \in X and t≥0t \ge0,

Pr⁡[BG(v,t)⊈QΔ(v)]≤b′tΔ,b′=αb\Pr[B_G(v,t) \not\subseteq\mathcal{Q}_{\Delta}(v)] \le b'\frac{t}{\Delta},\quad b'=\alpha b

We will skip the subscript GG from now on, and all distances and diameter are in the graph GG. Now, we are ready to prove the Lemma.

Proof. We build a nested padded hierarchy on a unit disk graph GG. For each 0≤j≤J=log⁡n0 \le j \le J=\log n, we independently sample a partition Qj\mathcal{Q}_j with Δ=2j\Delta=2^j. QJ={X}\mathcal{Q}_J=\{X\}.

For any 0≤j≤J0 \le j \le J, denote by Qj(v)\mathcal{Q}_j(v) the cluster in Qj\mathcal{Q}_j that contains vertex vv. Define the common intersection Rj(v)=⋂k=jJQk(v)R_j(v)=\bigcap_{k=j}^{J}\mathcal{Q}_k(v). If Rj(v)R_j(v) has multiple connected components, split the components into their own clusters. This provides a nested partition Pj\mathcal{P}_j. PJ={X}\mathcal{P}_J=\{X\}. These partitions have the following property: each cluster is connected and has diameter at most 2j2^j; Pj\mathcal{P}_j refines Pj+1\mathcal{P}_{j+1} – one cluster in Pj+1\mathcal{P}_{j+1} is decomposed into several clusters in Pj\mathcal{P}_j; each cluster in Pj\mathcal{P}_j is in a cluster of Qj\mathcal{Q}_j.

Last, a ball B(v,t)B(v,t) induces a connected subgraph. Consequently, if the ball is contained in every Qk(v)\mathcal{Q}_k(v), k≥jk\ge j, then it is contained in the connected component Pj(v)\mathcal{P}_j(v). By a union bound, we have

Pr⁡[B(v,t)⊈Pj(v)]≤∑k=jJ−1Pr⁡[B(v,t)⊈Qk(v)]≤∑k=j∞b′t2k=2b′t2j=2b′trj.(1)\Pr[B(v,t)\not\subseteq\mathcal{P}_j(v)]\le\sum_{k=j}^{J-1}\Pr[B(v,t)\not\subseteq\mathcal{Q}_k(v)]\le\sum_{k=j}^{\infty}b'\frac{t}{2^k}=2b'\frac{t}{2^j}=2b'\frac{t}{r_j}. \tag*{(1)}

For the setup of the Lemma, we will relate the pairs in EiE_i to the partition Pi\mathcal{P}_i. Consider a pair {p,q}\{p,q\} in EiE_i. Call the pair good if all three events hold:

B(p,ri16b′)⊆Pi(p),B\left(p,\frac{r_i}{16b'}\right)\subseteq\mathcal{P}_i(p),
B(q,ri16b′)⊆Pi(q),B\left(q,\frac{r_i}{16b'}\right)\subseteq\mathcal{P}_i(q),
B(p,Kri)⊆Pi+h(p),h=⌈log⁡2(16b′K)⌉,B(p,K r_i)\subseteq\mathcal{P}_{i+h}(p),\quad h=\left\lceil\log_2(16b'K)\right\rceil,

By Equation (1), the first two events fail with probability at most 1/81/8, and the third fails with probability at most 2b′K2h≤1/8\frac{2^{b'}K}{2^h} \le1/8. By the union bound, the probability that (p,q)(p,q) is good is at least 5/85/8. Let YiY_i be the expected number of good pairs at level ii. Yi≥∣Ei∣⋅5/8Y_i \ge|E_i| \cdot5/8. In the following, we will bound ∑i≥i0Yi\sum_{i \ge i_0} Y_i to be O(n)O(n). This will be enough for the lemma.

A good pair {p,q}\{p,q\} has the following property. Since d(p,q)≤Krid(p,q) \le Kr_i and the ball at pp of radius KriKr_i stays in a cluster Pi+h(p)\mathcal{P}_{i+h}(p), p,qp,q both stay in this cluster. Further, d(p,q)>rid(p,q) > r_i and clusters in Pi\mathcal{P}_i have diameter at most rir_i; pp and qq stay in different clusters in Pi\mathcal{P}_i. Last, since the ball at pp of radius ri/(16b′)r_i/(16b') stays in cluster Pi(p)\mathcal{P}_i(p), the cluster Pi(p)\mathcal{P}_i(p) has diameter at least ri/(16b′)−1≥ri/(32b′)r_i/(16b') - 1 \ge r_i/(32b'), if 2i≥(32b′)2^i \ge(32b'). To see why, follow the shortest path from pp to qq and stop at the last vertex zz right before exceeding distance ri/(16b′)r_i/(16b') from pp; zz stays in the cluster Pi(p)\mathcal{P}_i(p). Since the diameter of the cluster Pi(p)\mathcal{P}_i(p) is at least ri/(32b′)r_i/(32b'), it has at least ri/(32b′)r_i/(32b') vertices.

Now fix a cluster U∈Pi+hU \in\mathcal{P}_{i+h}. Let U1,…,UkU_1,\ldots,U_k be all the descendant clusters of UU in Pi\mathcal{P}_i and let tt be the number of these clusters with diameter at least ri/(32b′)r_i/(32b'). The number of good pairs that can be generated from the clusters {Uj}\{U_j\} is at most (t2)\binom{t}{2}. To bound this value, we use a potential function argument.

For any connected vertex set CC, we define a potential function

Φ(C)=2(∣C∣−1)−D(C)\Phi(C) = 2(|C|-1)-D(C)

Since CC is connected and each edge has weight at most 11, D(C)≤∣C∣−1D(C) \le|C|-1. Thus 0≤Φ(C)≤2(∣C∣−1)0 \le\Phi(C) \le2(|C|-1). Now suppose a cluster CC is partitioned into kk connected pieces C=C1⊎⋯⊎CkC=C_1 \uplus\cdots\uplus C_k. Consider the increase of the potential function

Γ(C)=Φ(C)−∑i=1kΦ(Ci)=2(k−1)+∑i=1kD(Ci)−D(C).(2)\Gamma(C) = \Phi(C)-\sum_{i=1}^{k}\Phi(C_i)=2(k-1)+\sum_{i=1}^{k}D(C_i)-D(C). \tag*{(2)}

Recall that CC and CiC_i are all connected subgraphs. If we shrink CiC_i to a supernode, the subgraph on CC has diameter at most k−1k-1. Thus D(C)≤∑i=1kD(Ci)+(k−1)D(C) \le\sum_{i=1}^{k}D(C_i)+(k-1). This means,

Γ(C)≥k−1≥0(3)\Gamma(C) \ge k-1 \ge0 \tag*{(3)}

The increase of the potential function provides an upper bound on k≥tk \ge t. Further, if we count all good pairs with different values of ii, the sum of the differences of the potential function allows telescoping, which provides the final O(n)O(n) bound. We explain the details next.

Now we are ready to bound the value (t2)\binom{t}{2}. Apply Equation (2) for our case of UU and its decomposition into U1,…,UkU_1,\ldots,U_k. we have

Γ(U)≥2(k−1)+ri⋅t16b′−2hri=2(k−1)+ri⋅(t16b′−2h)(4)\Gamma(U) \ge2(k-1)+r_i\cdot\frac{t}{16b'}-2^h r_i=2(k-1)+r_i\cdot\left(\frac{t}{16b'}-2^h\right) \tag*{(4)}

Now we do a case study of tt. If t/(16b′)≥2⋅2ht/(16b') \ge2\cdot2^h, by Equation (4) we have Γ(U)≥ri⋅t/(32b′)\Gamma(U) \ge r_i\cdot t/(32b'). Or, rit≤Γ(U)(32b′)r_i t \le\Gamma(U)(32b'). Since the point set has bounded density and UU has radius at most 2i+h2^{i+h}, we have ∣U∣≤A22(i+h)|U| \le A2^{2(i+h)} for some constant A≥1A \ge1. UU has tt subsets, each of at least ri/(32b′)r_i/(32b') vertices. Thus ∣U∣≥t⋅2i/(32b′)|U| \ge t\cdot2^i/(32b'). Combining the two inequalities, we have t≤A22h(32b′)rit \le A2^{2h}(32b')r_i. Altogether, we have

(t2)≤t22≤A222h(16b′)rit≤2A22h(16b′)2Γ(U)\binom{t}{2} \le\frac{t^2}{2} \le A^2 2^{2h}(16b')r_i t \le2A2^{2h}(16b')^2\Gamma(U)

If t/(16b′)<2⋅2ht/(16b') < 2\cdot2^h, apply Equation (3), we have

(t2)=t2(t−1)≤t2(k−1)≤16b′2hΓ(U)\binom{t}{2}=\frac{t}{2}(t-1)\le\frac{t}{2}(k-1)\le16b'2^h\Gamma(U)

Therefore, in both cases, we have 22h≤B⋅Γ(U)2^{2h} \le B \cdot\Gamma(U) for a constant B=2A22h(16b)2=O(K2)B = 2A2^{2h}(16b)^2 = O(K^2).

To bound the total number of good pairs at level ii, YiY_i, we now sum over all clusters in level i+hi+h. Define Fi=∑C∈PiΦ(C)F_i = \sum_{C\in\mathcal{P}_i} \Phi(C).

Yi≤B∑U∈Pi+hΓ(U)=B⋅(Fi+h−Fi)Y_i \le B \sum_{U\in\mathcal{P}_{i+h}} \Gamma(U) = B \cdot(F_{i+h} - F_i)

Now,

∑i≥i0Yi≤B∑i=0J(Fi+h−Fi)\sum_{i\ge i_0} Y_i \le B \sum_{i=0}^{J} (F_{i+h} - F_i)

Recall that the sum of the potential function increases as the level ii goes up. Fi≤Fi+1F_i \le F_{i+1}. PJ={X}\mathcal{P}_J = \{X\} and FJ=Φ(X)=2n−1−D(X)≤2nF_J = \Phi(X) = 2n - 1 - D(X) \le2n. Thus,

∑i≥i0Yi≤Bh⋅FJ=O(K2n)\sum_{i\ge i_0} Y_i \le Bh \cdot F_J = O(K^2n)

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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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.

Paper details

vlnc:W_9tw8p39a
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents