New Constructions of SSPDs and their Applications∗

Mohammad A. Abam† Sariel Har-Peled‡

March 29, 2018

Abstract
We present a new optimal construction of a semi-separated pair decomposition (i.e., SSPD) for
a set of n points in Rd . In the new construction each point participates in a few pairs, and it
extends easily to spaces with low doubling dimension. This is the first optimal construction with
these properties.
As an application of the new construction, for a fixed t > 1, we present a new construction of
a
t-spanner with O(n) edges and maximum degree O(log2 n) that has a separator of size O n1−1/d .

1 Introduction
For a point-set P, a pair decomposition of P is a set W of pairs of subsets of P, such that for every pair
of points of p, q ∈ P there exists a pair {X , Y} ∈ W such that p ∈ X and q ∈ Y—see Section 2 for the
formal definition. A well-separated pair decomposition (WSPD) of P is a pair decomposition of P such
that for every pair {X , Y}, the distance between X and Y is large when compared to the maximum
diameter of the two point sets. The notion of WSPD was developed by Callahan and Kosaraju [CK95],
and it provides a compact representation of the quadratic pairwise distances of the point-set P, since
there is a WSPD with a linear number of pairs.
P The total weight of a pair decomposition W is the total size of the sets involved; that is ω(W) =
{X ,Y}∈W (|X | + |Y|). Naturally, a WSPD with near linear weight is easier to manipulate and can be
used in applications where the total weight effects the overall performance. Unfortunately, it is easy
to see that, in the worst case, the total weight of any WSPD is Ω(n2 ). Callahan and Kosaraju [CK95]
overcame this issue by generating an implicit representation of the WSPD using a tree. Indeed, they
build a tree T (usually a compressed quadtree, or some other variant) that stores the points of the given
point set in the leaves. Pairs are reported as {u, v} where u and v are nodes in the tree such that their
respective pair S(u) ⊗ S(v) is well separated, where S(u) denotes the set of points stored at the subtree
of u.
∗
A preliminary version of this paper appeared in SoCG 2010 [AH10]. The latest version of this paper is available online
[AH10].
†
Department of Computer Engineering, Sharif University of Technology, Tehran, Iran. email:abam@sharif.edu.
‡
Department of Computer Science; University of Illinois; 201 N. Goodwin Avenue; Urbana, IL, 61801, USA;
sariel@uiuc.edu; http://www.uiuc.edu/~sariel/. Work on this paper was partially supported by a NSF AF award
CCF-0915984.

1
SSPDs. To overcome this obesity problem, a weaker notion of semi-separated
pair decomposition (SSPD) had been suggested by Varadarajan [Var98]. Here,
Y
an SSPD S of a point set has the property that for each pair {X , Y} ∈ S the
distance between X and Y is large when compared to the minimum diameter of
the two point sets (in the WSPD case this was the maximum of the diameters). X
See figure on the right for an example of a semi-separated pair that is not well-
separated.

By weakening the separation, one can get an SSPD with near-linear total weight. Specifically,
Varadarajan [Var98] showed how to compute an SSPD of weight O n log n for a set of n points in
4

the plane, in O(n log5 n) time (for a constant separation factor). He used the SSPD for speeding up his
algorithm for the min-cost perfect-matching in the plane. Recently, Abam et al. [AdBFG09] presented
an algorithm which improves the construction time to O(ε−2 n log n) and the weight to O(ε−2 n log n),
where 1/ε is the separation required between pairs. It is known that any pair decomposition has weight
Ω(n log n) [BS07], implying that the result of Abam et al. [AdBFG09] is optimal. This construction
was generalized to Rd with the construction time being O(ε−d n log n) and the total weight of the SSPD
being O(ε−d n log n), see [AdBF+ 11].

Spanners. More recently SSPDs were used in constructing certain geometric spanners [AdBFG09,
AdBF+ 11, ACFS09]. Let G = (P, E) be a geometric graph on a set P of n points in Rd . That is, G is
an edge-weighted graph where the weight of an edge pq ∈ E is the Euclidean distance between p and q.
The distance in G between two points p and q, denoted by dG (p, q), is the length of the shortest (that is,
minimum-weight) path between p and q in G. A graph G is a (geometric) t-spanner, for some t ≥ 1,
if for any two points p, q ∈ P we have dG (p, q) ≤ t · kpqk. Note that the concept of geometric spanners
can be easily extended to any metric space. Geometric spanners have received considerable attention
in the past few years—see [NS07] and references therein. Obviously, the complete graph is a t-spanner,
but a preferable spanner would provide short paths between its nodes, while having few edges. Other
properties considered include (i) low total length of edges, (ii) low diameter, (iii) low maximum degree,
and (iv) having small separators.

Separators. A graph G is said to have a k-separator if its vertices can be decomposed into three
sets X , Y and Z such that both |X | and |Y| are Ω(n) and |Z| ≤ k (i.e., the set Z is the separator). Fur-
thermore, there is no edge in G connecting a vertex in X to a vertex in Y. Graphs with good separators
are the best candidates to applying the divide and conquer approach—see [LT80, MTTV97, SW98] and
references therein
√ for

more results and applications. Lipton and Tarjan [LT80] showed that any planar
graph has an O n -separator. The Delaunay triangulation of a planar point-set √ P is an O(1)-spanner
[KG92]. Furthermore, it is a planar graph and is thus an O(1)-spanner with an O( n)-separator. Fürer
and Kasiviswanathan [FK07] recently presented a t-spanner for a ball
graph which is an intersection
graph of a set of n ball in Rd with arbitrary radii which has an O n1−1/d -separator. Since complete Eu-
clidean graphs are a special case of unit ball graphs, their results yields a new construction of t-spanner
for geometric graphs with small separators.

Metric spaces with low doubling dimension. Recently the notion of doubling dimension [Ass83,
GKL03, Hei01] which is a generalization of the Euclidean dimension, has received considerable attention.
The doubling constant of a metric space M is the maximum, over all balls b in the metric space M, of

2
the minimum number of balls needed to cover b, using balls with half the radius of b. The logarithm
of the doubling constant is the doubling dimension of the space—note that Rd has Θ(d) doubling
dimension. Constructions of WSPD, spanners, and a data-structure for approximate nearest neighbor
for metric spaces with fixed doubling dimension were provided by Har-Peled and Mendel [HM06].

Limitations of known constructions of SSPDs. The optimal construction of SSPDs of [AdBFG09]

uses BAR-trees [DGK01], and as such it is not applicable to metric spaces with constant doubling
dimension. Moreover, in all previously known optimal constructions of SSPDs a point might appear in
many (i.e., linear number of) pairs, see Appendix B for an example demonstrating this. Note, that in
Varadarajan’s original construction [Var98] a point might appear in a O(log4 n) pairs (for the planar
case). In particular, in all previous constructions of spanners with small separators the degree of a point
might be Ω(n).

Our results. Interestingly, building an SSPD for a point set with polynomially bounded spread is
relatively easy, as we point out in Section 2 (see Remark 2.9). However, extending this construction to
the unbounded spread is more challenging. Intuitively, this is because the standard WSPD construction
is local and greedy in nature, and does not take the global structure of the point set into account (in
particular, it ignore weight issues all together), which is necessary when handling unbounded spread.
Building upon this bounded spread construction, we present two new constructions of
SSPDs for
a point set in Rd . The first construction guarantees that each point appears in O log2 n pairs and
the resulting SSPD has weight O n log n . This construction is (arguably) simpler than previous
2

constructions.
The second construction uses a randomized partition scheme, which is of independent interest, and
results in an optimal SSPD where each point appears in O(log n) pairs, with high probability. This is the
first construction to guarantee that no point participates in too many pairs. The two new constructions
of SSPDs work also in finite metric spaces with low doubling dimension. This enables us to extend, in a
plug and play fashion, several results from Euclidean space to spaces with low doubling dimension—see
Section 5.1 for details.
We also present an algorithm for constructing a spanner in Euclidean space from any SSPD. Since
this is a simple generalization of the algorithm given in [AdBFG09], we delegate the description of this
algorithm to Appendix A. The new proof showing that the output graph is t-spanner is independent of
the SSPD construction, unlike the previous proof of Abam et al. [AdBFG09].
Using the new constructions, for
a fixed t, we present a new construction of a t-spanner

with O(n)
edges and maximum
degree O log n . The construction of this spanner takes O n log n time, and it
2 2

contains an O n1−1/d -separators. Note that, in the worst case, the separator can not be much smaller.
The previous construction of Fürer and Kasiviswanathan [FK07] is slower, and the maximum degree in
the resulting spanner is unbounded—see Theorem 5.7 for details.

The paper is organized as follows: In Section 2, we formally define some of the concepts we need and
prove some basic lemmas. Section 3 presents a simple construction of SSPDs. In Section 4, we present
the new optimal construction of SSPDs. In Section 5, we present the new construction of a spanner with
a small separator. We depart with a few concluding remarks in Section 6.

3
2 Preliminaries
Definitions
and notation. Let b(p, r) denote the closed ball centered at a point p of radius r. Let
ring p, r, R = b(p, R) \ b(p, r) denote the ring centered at p with outer radius R and inner radius r.
For two sets of points P and Q in Rnd , we denote the distance betweeno the sets P and Q by d(P, Q) =
min kp − qk. We also use P ⊗ Q = {p, q} p ∈ P, q ∈ Q and p 6= q to denote all the (unordered)
p∈P,q∈Q
pairs of points formed by the sets P and Q.

Definition
 2.1 (Pair decomposition.). For a point-set P, a pair decomposition of P is a set of pairs
W = {X1 , Y1 } , . . . , {Xs , Ys } , such that (i) Xi , Yi ⊂ P for every i, (ii) Xi ∩ Yi = ∅ for every i, and
(iii) ∪si=1 Xi ⊗ Yi = P ⊗ P.
The weight of a pair decomposition W is defined to be ω(W) = si=1 (|Xi | + |Yi |).
P

As mentioned in the introduction, such a pair decomposition is usually described implicitly by

reporting pairs {u, v} where u and v are nodes of a tree T that stores the points of the given point set
in the leaves and is used to construct the decomposition. As such, a pair {u, v} represents the pairs
S(u) ⊗ S(v), where S(u) is the set of points stored in the subtree of u.

Definition 2.2. A pair of sets R and S is (1/ε)-separated if max(diam(R) , diam(S)) ≤ ε · d(R, S). Fur-
thermore, they are (1/ε)-semi-separated if min(diam(R) , diam(S)) ≤ ε · d(R, S).

Definition 2.3 (WSPD). For a point-set P, a well-separated pair decomposition of P with parameter
1/ε is a pair decomposition W of P, such that for any pair {Xi , Yi } ∈ W, the sets Xi and Yi are
(1/ε)-separated.

Definition 2.4 (SSPD). For a point-set P, a semi-separated pair decomposition of P with parameter
1/ε, denoted by (1/ε)-SSPD, is a pair decomposition of P formed by a set of pairs S, such that all the
pairs of S are (1/ε)-semi-separated.

Note that, by definition, a (1/ε)-WSPD of P is also a (1/ε)-SSPD for P. Interestingly, one can split
any pair decomposition such that it covers only pairs that appear in some desired cut.

Lemma 2.5. Given any pair decomposition W of a point-set P, and given a subset Q, one can compute
a pair decomposition W 0 for Q ⊗ Q (that covers only these pairs), where Q = P \ Q. Furthermore, the
following properties hold.
(A) If a point appears in k pairs of W then it appears in at most k pairs of W 0 .
(B) We have ω(W 0 ) ≤ ω(W).
(C) The number of pairs in W 0 is at most twice the number of pairs in W.
(D) For any pair {X 0 , Y 0 } ∈ W 0 there exists a pair {X , Y} ∈ W such that X 0 ⊆ X and Y 0 ⊆ Y.
(E) The time to compute W 0 is linear in the weight of W.
n o
Proof: Let W =0
X ∩ Q, Y ∩ Q , X ∩ Q, Y ∩ Q {X , Y} ∈ W . Naturally, we can throw away


pairs {X, Y } ∈ W such that X or Y are empty sets. It is now easy to check that the above properties
0

hold for the pair decomposition W 0 .

We need the following easy partition lemma.

4
Lemma 2.6 ([HM06]). Given any set P of n points in Rd , an any constant µ ≥ 1, and a sufficiently
large constant c ≥ 1 (that depends only on µ and the dimension d), one can compute, in expected linear
time, a ball b(p, r) that contains at least n/c points of P, such that b(p, µr) contains at most n/2 points
of P, where p ∈ P.

Proof: We include the proof for the sake of completeness. Pick randomly a point p from P, and compute
the ball b(p, r) of smallest radius around p containing at least n/c points of P. Next, consider the ball
of radius b(p, µr). If it contains at most n/2 points of P, then we are done. Otherwise, we repeat this
procedure until we succeed.
To see why this algorithm succeeds with constant probability in each iteration, consider the smallest
radius ball that contains at least m = n/c points of P and is centered at a point of P. Let q ∈ P be its
center, ropt be its radius, and let Q = P ∩ b(q, ropt ) be the points of P contained in this ball. Observe
that any ball of radius ropt /2 contains less than m points (the ball is not necessarily centered at a point
of P). With probability ≥ 1/c, we have that p is in Q; if this is the case, then r ≤ 2ropt .
Furthermore, the ball b(p, µropt ) can be covered by O(1) balls of radius ropt /2. Indeed, consider
the axis
√ parallel box of sidelength 2µropt centered at p, and partition it into a grid with sidelength
ropt / d. Observe that every grid cell can be covered by a ball of radius ropt /2, and this grid has at
√  √ d
most c0 = (2µropt /(ropt / d) + 1)d = 2µ d + 1 cells. Hence it holds that |P ∩ b(p, µr)| < c0 m ≤ n/2,
by requiring that c ≥ 2c0 .
Thus, the algorithm succeeds with probability 1/c in each iteration, and the expected number of
iterations performed is O(c). This implies the result, as each iteration takes O(n) time.

The following partition lemma is one of the key ingredients in the new SSPD construction.

Lemma 2.7. Let P be a set of n points in Rd , t > 0 be a parameter, and let c be a sufficiently
large constant. Then one
can compute in linear time a ball b = b(p, r), such that (i) |b ∩ P| ≥ n/c,
(ii) ring p, r, r(1 + 1/t) ∩ P ≤ n/2t, and (iii) |P \ b(p, 2r)| ≥ n/2.

Proof: Let b = b(p, α) be the ball computed, in O(n) time, by Lemma 2.6 such that |b(p, α) ∩ P| ≥ n/c
and |b(p, 8α) ∩ P| ≤ n/2. We will set r ∈ [α, eα] in such a way that property (ii) will
hold for it. Indeed,
set ri = α(1 + 1/t) , for i = 0, . . . , t, and consider the rings Ri = ring p, ri−1 , ri , for i = 1, . . . , t. We
i

have that rt = α(1 + 1/t)t ≤ α(exp(1/t))t ≤ αe, since 1 + x ≤ ex for all x ≥ 0. As such, all these
(interior disjoint) rings are contained inside b(p, 4α). It follows that one of these rings, say the ith ring
Ri , contains at most (n/2)/t of the points of P (since b(p, 8α) contains at most half of the points of P).
For r = ri−1 ≤ 4α the ball b = b(p, r) has the required properties, as b(p, 2r) ⊆ b(p, 8α).

2.1 WSPD construction for the bounded spread case


  
The spread of a point-set P is the quantity Φ(P) = max kpqk / min kpqk . We next describe
p,q∈P p,q∈P,p6=q
a simple WSPD construction whose weight depends on the spread of the point set. The idea is to use a
regular quadtree of height O(log Φ) to compute the WSPD, and observe that each node participates in
O(1/εd ) pairs.

Lemma 2.8. Let P be a set of n points in Rd , with spread Φ = Φ(P), and let ε > 0 be a parameter.
Then, one can compute a (1/ε)-WSPD (and thus a (1/ε)-SSPD)
for P of total weight O(nε log Φ).
−d

Furthermore, any point of P participates in at most O ε log Φ pairs.

−d

5
Proof: Build a regular (i.e., not compressed) quadtree for P and observe that its height is h = O(log Φ).
To avoid some minor technicalities, if a leaf contains a point of P and its height < h then continue
refining it till it is of height h. Now, all the leafs of the quadtree that have a point of P stored in them
are of the same height h. Clearly, the time to construct this quadtree is O(n log Φ)
Now, construct a (1/ε)-WSPD for P using this quadtree, such that a node participates only in pairs
with nodes that are of the exact same level in the quadtree. This requires a slight modification of the
algorithm of [CK95], such that if it fails to separate the pair of nodes {u, v}, then it recursively tries
to separate all the children of u from all the children of v, thus keeping the invariant that all the pairs
considered involve nodes of the same level of the quadtree.
We claim that every node participates in O(ε−d ) pairs in the resulting WSPD. Indeed, a WSPD pair
{u, v} corresponds to two cells u and v that are cubes of the same size, such that diam(u ) /ε ≤
d(u , v ). However, for such a pair, we must also have that d(u , v ) ≤ 4d · diam(u ) /ε. Otherwise,
the parents of u and v would be (1/ε)-separated, and the algorithm would use them as a pair instead of
{u, v}.
As such, all the pairs involving a node u in the quadtree must use nodes in the same level of the
quadtree, and they are in a ring of radius Θ(diam(u ) /ε) around it. Clearly, there are O(1/εd ) such
nodes. Implying that u participates in at most O(1/εd ) pairs.
Now, a point p ∈ P participates in pairs involving nodes v, such that v is on the path of p from
its leaf to the

root of the quadtree. As such, there are O(log Φ) such nodes, and p will appear in U =
O ε log Φ pairs in the WSPD. This implies that the total weight of this WSPD is nU = O nε log Φ ,
−d −d

as claimed.

Remark 2.9. Lemma 2.8 implies the desired result (i.e., an SSPD with low weight) if the spread of P is
polynomial in |P|.

Remark 2.10. In Lemma 2.8, by forcing the (1/ε)-WSPD to form pairs only between nodes in the same
level of the quadtree, the resulting WSPD has the property that each node of the quadtree participates
in O(1/εd ) pairs.

3 A simple construction of SSPDs

We first describe a simple construction of SSPDs for a point-set P, which is suboptimal.
Theorem 3.1. Let P be a set of n points in Rd , and let ε > 0 be a parameter. Then, one can compute
a (1/ε)-SSPD for P of total weight O(nε−d log2 n).

Proof: Using Lemma 2.7, with t = n, we compute a ball b(p, r) that contains at least n/c points of P,
and such that ring p, r, (1 + 1/2t)r contains at most bn/2tc = b1/2c = 0

points of P (that is, this ring contains no point of

ring p, r, 2r/ε

P).
Let Pin = P∩b(p, r), Pout = P∩ring p, r, 2r/ε , and Pouter = P\(Pin ∪ Pout ), Pin
see figure on the right. Clearly, {Pin , Pouter } is a (1/ε)-semi-separated pair,
2r/ε
which we add to our SSPD. Let ` = d(Pin , Pout ) and observe that ` ≥ r/2n. p r
We would like to compute the SSPD for all pairs of points in X = Pin ⊗Pout .
Observe that none of these pairs has length smaller than `, and the diameter of Pout
the point-set Q = Pin ∪ Pout is diam(Q)
√ ≤ 4`n/ε. Thus, we can snap the point- Pouter
set Q to a grid of sidelength ε`/2 d. The resulting point-set Q0 has spread
O(n/ε2 ). Next, compute a (2/ε)-SSPD for the snapped point-set Q0 , using the algorithm of Lemma 2.8.

6
Clearly, the computed SSPD when interpreted on the original point-set Q would cover all the pairs of X,
and it would provide an (1/ε)-SSPD for these pairs. By Lemma 2.8, every point of Q would participate
in at most O ε−d log(n/ε) = O ε−d log n pairs.

To complete the construction, we need to construct a (1/ε)-SSPD for the

pairs Pin ⊗ Pin and (Pout ∪ Pouter ) ⊗ (Pout ∪ Pouter ). To this end, we continue


ring p, r, 2r/ε
the construction recursively on the point-sets Pin and Pout ∪ Pouter . Pin
In the resulting SSPD, every point participates in at most T (n) = 1 +
2r/ε
O ε log n + max(T (n1 ), T (n2 )) , where n1 = |Pin | and n2 = |Pout ∪ Pouter |.
−d r


p
Since n1 + n2 = n and
n1 , n2 ≥ n/c, where c is some constant. It follows that
T (n) = O ε−d log2 n . Now, a point participates in at most T (n) pairs, and as Pout
such the total weight of the SSPD is O(nT (n)), as claimed. Pouter

4 An optimal construction of SSPDs

4.1 The construction
Let P be a set of n points in Rd . If n = O(1/εd ) then we compute a (1/ε)-WSPD of the point set and
return it as the SSPD. Otherwise, we compute a ball b(p, r) that contains at least n/c points of P and
such that P \ b(p, 20r) contains at least n/2 of the points of P, where c is a sufficiently large constant
that depends only on the dimension d.
We randomly choose a number x in the range [5r, 6r], and consider the sets:


Pin = P ∩ b(p, x) , Pout = P ∩ ring p, x, 20r ,
and

r
Pouter = P \ Pin ∪ Pout . 20r
p x
Pin
We recursively compute an SSPD for the set Pin and an SSPD for the set Pout ∪ Pout
Pouter . Pouter

It remains to separate all the pairs of points in Pin ⊗(Pout ∪ Pouter ). We do this in two steps, and
merge all these pair decompositions together to get the desired SSPD of P.

4.1.1 Separating Pin from Pouter

Partition the points of Pin into O(1/εd ) clusters, such that each cluster has diameter ≤ εr/20. Clearly,
we need m = O(1/εd ) such clusters C100 , . . . , Cm
00
. Now, since d(Ci00 , Pouter ) ≥ r, it follows that Ci00 and
Pouter are (1/ε)-semi-separated, for all i. Therefore, we create the pair separating Ci ⊗ Pouter , for all i.
Each point of P participates in O(1/εd ) such pairs.
We will refer to all the pairs generated in this stage as being long pairs.

4.1.2 Separating Pin from Pout

This is the more challenging partition to implement as there is no gap between the two sets. We build
a quadtree T for R = Pin ∪ Pout = P ∩ b(p, 20r) and compute a 1/ρ-WSPD on this quadtree, where
ρ = ε/4. Namely, a pair in this decomposition is a pair of two nodes u and v in the quadtree T, such
that diam(u ) = diam(v ) ≤ (1/ρ)d(u , v ), where u and v denote the cells in Rd that u and v
corresponds to. The construction outputs only the pairs {u, v} such that S(u) ⊗ S(v) contains at least

7
one pair of Pin ⊗ Pout (i.e., the other pairs of this WSPD are being ignored). The details of how to do
this efficiently are described next.
We refer to all the pairs generated in this stage as being short pairs.

On the fly computation of the quadtree. To do the above efficiently we do not compute the
quadtree T in advance. Rather, we start with a root node containing all the points of R. Whenever the
algorithm for computing the pair decomposition tries to access a child of a node v, such that v exists in
the tree but not its children, we compute the children of v, and split the points currently stored in v (i.e.,
S(v)) into the children of v. For such newly created child w, we check if S(w) ⊆ Pin or S(w) ⊆ Pout (and
if so, we turn on the relevant flags in w). Then the regular execution of the algorithm for computing a
pair decomposition resumes.

On the fly pruning of pairs considered. Whenever the algorithm handles a pair of vertices u, v of
T, it first checks if S(u) , S(v) ⊆ Pin or S(u) , S(v) ⊆ Pout , and if so, the algorithm returns immediately
without generating any pair (i.e., all the pairs that can be generated from this recursive call do not
separate points of Pin from Pout and as such they are not relevant for the task at hand). Using the
precomputed flags at the nodes of T this check can be done in constant time. (A similar idea of doing
on the fly implicit construction of a quadtree while generating some subset of a pair decomposition was
used by Har-Peled [Har01].)

Generating pairs that belong to the same level. Note that since we are using a regular quadtree
to compute the pair decomposition, we can guarantee that any pair of nodes {u, v} realizing a pair (i.e.,
S(u) ⊗ S(v)) belongs to the same level of the quadtree. Namely, the sidelength of the two cells u
and v is the same. (It is easy to verify that using a regular quadtree to construct WSPD, instead of
compressed quadtrees, increases the number of pairs in the WSPD only by a constant factor.)

Cleaning up. Finally, we need to guarantee that only pairs in Pin ⊗ Pout are covered by this generated
(partial) pair decomposition. To this end, we use the splitting algorithm described in the proof of
Lemma 2.5 to get this property.

4.2 Analysis
4.2.1 Separating Pin from Pout
We first analyze the weight of the pairs in the SSPD separating Pin from Pout . Let R = P ∩ b(p, 20r), and
for a point q ∈ R, let Dq be the random variable which is the (signed) distance of q from the boundary
of the ball b(p, x). Formally, we have
Dq = kp − qk − x.
For each specific point q, the random variable Dq is uniformly distributed in an interval of length r
(note, that for different points this interval is different).

Claim 4.1. Consider a point q ∈ R, and a pair of nodes of the quadtree {u,v} that is in the generated
1 1 r
SSPD of Pin ⊗ Pout and such that q ∈ S(u). Then depth(u) = depth(v) ∈ lg , lg + β + lg ,
ε ε |Dq |
where β is some constant. The level depth(u) is active for q, and the number of active levels in the
quadtree for q is bounded by ν(q) = 1 + β + lg |Drq | .

8
Proof: Assume that q ∈ Pin (a symmetric argument would work for the case that q ∈ Pout ), and observe
that q is in distance at least |Dq | from all the points of Pout . Consider any pair of nodes of the quadtree
u and v such that: (i) u and v are in the same level in the quadtree, (ii) q ∈ S(u), (iii) the cells of u
and v have diameter ∆ = diam(u ) = diam(v ), such that ∆ ≤ ε |Dq | /c (for c to be specified shortly),
and (iv) S(v) ∩ Pout 6= ∅. Now, u and v have the same side length, and the distance between the two
cells is at least
 
d

2ε |Dq | 2ε c ε c − 2ε
d(u , v ) ≥ d q, R \ b(p, x) − 2∆ ≥ |Dq | − = 1− · |Dq | ≥ ∆.
c c ε c ε

Namely, u and v are α–separated, for α = (c − 2ε) /ε. In particular, by picking c to be sufficiently large,
we can guarantee that their respective parents p (u) and p (v) are α/4-separated, and α/4 ≥ 1/ρ. This
implies that p (u) and p (v) are 1/ρ-separated, and the algorithm would have included {p (u) , p (v)} in
the SSPD, never generating the pair {u, v}.
Namely, a node u in the quadtree that contains q and also participates in an SSPD pair, has
diam(u ) ≥ ε |Dq | /c. As such, the node u has depth at most

diam(Pin ∪ Pout ) 40r 1 r

O(1) + lg = O(1) + lg = O(1) + lg + lg ,
ε |Dq | /c ε |Dq | /c ε |Dq |
as claimed.
As for the lower bound – let diam(R) denote the diameter of diam(R). To get a (1/ρ)-separation of
any two pointsof R, one needs
 to use cells with diameter ≤ ρ diam(R). The depth of such nodes in the
diam(R) 1
quadtree is ≥ lg ≥ lg , as claimed.
ρ diam(R) ε
 
r
Claim 4.2. For a point q ∈ R we have that E lg = O(1).
|Dq |

Proof: Let I be the interval of length r, such that Dq is distributed uniformly in I. Clearly i ≤ lg |Drq | ≤
h i
i + 1 if and only if r2−i−1 ≤ |Dq | ≤ r2−i . Namely, Dq ∈ Ji or Dq ∈ −Ji , where Ji = r2−i−1 , r2−i .
Therefore,
 
r 2 |Ji | 1
Pr i ≤ lg ≤i+1 ≤ ≤ i, (1)
|Dq | r 2
  X ∞
r 1
and E lg ≤ (i + 1) · i = O(1).
|Dq | i=0
2

Lemma 4.3. The expected total weight of the pairs of the SSPD of Pin ⊗ Pout is O(n/εd ).

Proof: By Claim 4.1 we have that every point q ∈ R (in expectation) participates in nodes that have
depth in the range lg ε , X + O(1) + lg ε , where X = lg |Drq | . Now, since every node of the regular
1 1


quadtree participates in at most O(1/εd ) WSPD pairs (in the same level, see
 Remark
h 2.10),
iwe conclude
that q participates in O((1 + X)/ε ) pairs. By Claim 4.2, we have that O E (1 + X)/ε
d d
= O(1/εd ).
The claim now follows by summing this up over all the points of R.

Lemma 4.4. The expected time to compute pairs of the SSPD of Pin ⊗ Pout is O(n/εd ).

9
Proof: We break the running time analysis into two parts. First, we bound the time to compute (the
partial) quadtree T. Observe that this can be charged to the time spend moving the points down the
quadtree. Arguing as in Claim 4.1, a point q ∈ R is contained in pairs considered by the algorithm with
1 r
maximum depth Yq = O(1) + lg + lg . In particular, the maximum depth of q in T is Yq + 1.
ε |Dq |
Indeed, q is pushed down the quadtree only when the algorithm is trying to separate a pair of nodes
{u,
hPv} suchithat q ∈ S(u) or q ∈ S(v). As such, the expected time to compute T is proportional to
E q∈R Yq , which by Claim 4.2, and linearity of expectations, is O(n log(1/ε)).
Secondly, we need to bound the time it takes to generate the pairs themselves. First, observe that
the algorithm considers only pairs of nodes that are in the same level of the quadtree. Now, for a specific
node u of the quadtree T the total number of nodes participating in pairs considered (by the algorithm),
that include u and are in the same level as u is O(1/εd ). In particular, we bound by O(1/ε2d ) = O(n/εd )
the total time spend by the algorithm in handling pairs that are in the top α = blg 1/εc levels of the
quadtree.
To bound the remaining work, consider a point q and all the recursive calls in the algorithm that
consider nodes that contain q. The total recursive work that q is involved in is bounded by O(Yq /εd ).
However, by the above, we can ignore the work involved by the top α levels. As such, the total work
in identifying the generated pairs involving q is bounded by O((Yq − α)/εd ). And in expectation, by
Claim 4.2, this is O(1/εd ), and O(n/εd ) overall.

4.2.2 Bounding the total weight

Lemma 4.5. In the SSPD computed, every point participates in O(ε−d log n) long pairs.

Proof: The depth of the recursion is O(log n). A point is being sent only to a single recursive call.
Furthermore, at each level of the recursion, a point might participate in at most O(ε−d ) long pairs.

Lemma 4.6. In the SSPD computed, every point participates in O(ε−d log n) short pairs, both in expec-
tation and with high probability.

Proof: Consider a point q ∈ P, and let Xk be the number of short pairs it appears in when considering
the subproblem containing it in the kth level of the recursion. By Claim 4.1 and Claim 4.2, we have
that       
ν(q) 1 r 1 + Zk
Xk = O = O d 1 + lg =O ,
εd ε |Dq | εd
where Zk = lg |Drq | is dominated by a geometric variable with expectation O(1) (see Eq. (1)). Therefore,
the number of pairs q participates in is bounded by a sum of h geometric variables, each one with
expectation O(1/εd ), where h = O(log n) is the depth of the recursion. These variable arise from
different levels of the recursion, and are as such independent. Now, there are Chernoff type inequalities
for such summations that immediately imply the claim—see [MR95].

Lemma 4.7. Given a point-set P in Rd , and parameter ε >
0, one can compute, in expected time
O(nε−d log n),
an SSPD of P of total expected weight O nε−d log n . Furthermore, every point participates
in O ε−d log n pairs with high probability.

Proof: The bound on the total weight of the SSPD generated is implied by Lemma 4.5 and Lemma 4.6.
As for the running time, Lemma 4.4 implies that in expectation the divide stage takes O(n/εd ) time,
and since the two subproblems have size which is a constant fraction of n, the result follows.

10
4.2.3 Reducing the number of pairs
In the worst case, the above construction would yield Ωε (n log n) pairs (here Ωε hides constants that
depends polynomially on ε). Fortunately, one can reduce the number of pairs generated. The idea is to
merge together pairs of the SSPD that are still well separated together.
We need the following technical lemma.

Lemma 4.8. Let ε ≤ 1/12 and ε0 ≤ ε/6 be parameters, let X, Y be a (1/ε)-separated pair, and let Xi , Yi
be (1/ε0 )-separated pairs, for i = 1, . . . , k. Furthermore, assume that for all i, we have X ∩ Xi 6= ∅ and
Y ∩ Yi 6= ∅. Then X = ∪i Xi is (1/4ε)-separated from Y = ∪i Yi .

Proof: Let x ∈ X and y ∈ Y be the pair of points realizing ` = d(X, Y ). Similarly, for all i, let `i =
d(Xi , Yi ). By Definition 2.2, for all i, we have that (i) diam(X) ≤ ε`, (ii) diam(Y ) ≤ ε`, (iii) diam(Xi ) ≤
ε0 `i , and (iv) diam(Yi ) ≤ ε0 `i .
We also have that `i ≤ d X ∩ Xi , Y ∩ Yi ≤ ` + diam(X) + diam(Y ) ≤ (1 + 2ε)`. In particular, as

X and Xi have a non-empty intersection, we have that Xi (resp. Yi ) is contained in a ball of radius
diam(X) + diam(Xi ) ≤ r = ε` + ε0 `i centered at x (resp. y). As such, X and Y are contained in balls of
radius r centered at x and y, respectively. The distance between these two balls is at least ` − 2r, and
the diameter of these two balls is 2r. As such, X and Y are 1/τ -separated for

max(diam(X) , diam(Y)) 2r 2ε` + 2ε0 `i 2ε` + 2ε0 (1 + 2ε)`

τ= ≤ = ≤
d(X, Y) ` − 2r ` − 2ε` − 2ε0 `i ` − 2ε` − 2ε0 (1 + 2ε)`
2ε + 2ε0 (1 + 2ε) 3ε
= 0
≤ ≤ 4ε,
1 − 2ε − 2ε (1 + 2ε) 1 − 3ε

as ε ≤ 1/12 and ε0 ≤ ε/6.

Lemma 4.9. Given an O(1/ε)-SSPD (similar to the one constructed above) with total weight O(nε−d log n),
one can reduce the number of pairs in the SSPD to O(n/εd ), and this can be done in O(nε−d log n) time.

Proof: The number of long pairs created is clearly O(n/εd ), as the divide stage generates O(1/εd ) long
pairs, and the recursive construction stops when the size of the subproblem drops below O(1/εd ).
Let S be the computed O(1/ε)-SSPD (we require a slightly stronger separation to implement this
part). We are going to merge only the short pairs computed by the algorithm. Observe, that the short
pairs in S are all O(1/ε)-separated (i.e., not only semi-separated). Construct a O(1/ε)-WSPD W of the
point-set P. For each short pair A ⊗ B ∈ S, pick an arbitrary point q ∈ A and r ∈ B, and find the pair
X ⊗ Y in W such that q ∈ X and r ∈ Y . Associate the pair A ⊗ B with the pair X ⊗ Y . Repeat this
for all the pairs in S.
Given a pair of points q, r finding the pair of the WSPD containing the two points can be done in
constant time [FMS03]1 . As such, we can compute, in O((n/εd ) log n) time, for all the short pairs in the
SSPD S its associated pair in the WSPD. Now, take all the SSPD pairs {X1 , Y1 } , . . . , {Xk , Yk } that are
associated with a single pair {X, Y } of the WSPD, such that Xi ∩ X 6= ∅ and Yi ∩ Y 6= ∅ for all i. We
replace all these short pairs in the SSPD S by the single pair
! !
X ⊗ Y where X = and Y =
[ [
Xi Yi .
i i

1
This result uses hashing and the floor function.

11
By Lemma 4.8, X and Y are 1/ε-separated. As such, in the end of this replacement process, we have
a 1/ε-SSPD that has O(n/εd ) long pairs and |W| short pairs, where |W| is the number of pairs in the
WSPD W. Overall, this merge process takes time that is proportional to the total weight of the original
SSPD.
Thus, we get a SSPD that has O(n/εd ) pairs overall, and clearly this merging process did not increase
the total weight of the SSPD.

4.3 The results

Putting the above together we get our main result.

Theorem 4.10. Given a point-set P in Rd , and parameter ε > 0, one can compute, in O(nε−d log n)
expected time, an SSPD S of P, such that: (A) The total expected weight of the pairs of S is O nε−d log n .

(B) Every point of P participates in O ε−d log n pairs, with high probability. (C) The total number of

pairs in S is O(n/εd ).

One can extend the result also to an n-point metric space with bounded doubling dimension.

Theorem 4.11. Let P be an n-point metric space with doubling dimension dim, and parameter ε > 0,
then one can compute, in O(nε−O(dim) log n) expected
time, an SSPD S of P, such that: (A) −O(dim)
The total ex-

pected weight of the pairs of S is O nε−O(dim)
log n . (B) Every point of P participates in O
ε log n
pairs, with high probability. Furthermore, by investing an additional O nε−O(dim) log2 n time one can
reduce the number of pairs in S to O(n/εd ).

Proof: This follows by an immediate plug and chug of our algorithm into the machinery of Har-Peled
and Mendel [HM06]. Observe that our algorithm only used distances in the computation. In particular,
we replace the use of quadtrees by net-trees, see [HM06].
The deterioration in the running time to reduce the number of pairs is caused by the longer time it
takes to perform a “pair-location” query; that is, locating the pair containing a specific pair of points
takes O(log n) time instead of constant time.

It seems that by redesigning the algorithm one can remove the extra log factor needed to reduce the
number of pairs in the resulting SSPD. However, the resulting algorithm is somewhat more involved and
less clear, and we decided to present here the slightly less efficient variant.

5 Applications
5.1 Immediate applications
We now have a near-linear weight SSPD for any point set from a finite metric space with low doubling
dimension. We can use this SSPD in any application that uses only the SSPD property, and do not use
any special properties that exist only in Euclidean space. So, let P be an n-point metric space with
constant doubling dimension. By plugging in the above construction we get the following new results:
(A) A (1 + ε)-spanner for P with (hopping) diameter 2 and Oε (n log n) edges [ACFS09], where Oε (·)
hides constants that depends polynomially on 1/ε.
(B) A (3 + ε)-spanner of a complete bipartite graph [ACFS09]. (This can also be done directly by using
WSPD.)

12
(C) An additively (2 + ε)-spanner with Oε (n log n) edges [AdBF+ 11] can be constructed for P. See
[AdBF+ 11] for exact definitions.
The previous results mentioned above were restricted to points lying in Rd , while the new results also
works in spaces with low doubling dimension.
One can also extract a spanner from any SSPD, as the following theorem states. Since the proof of
this is standard, we delegate the proof to Appendix A.

Theorem 5.1. Given a 8/ε-SSPD S for a point-set P in Rd , one can compute a (1 + ε)-spanner of P
with O(|S| /εd−1 ) edges. The construction time is proportional
to the total weight of S. In particular, a
point appearing in k pairs of the SSPD is of degree O k/εd−1 in the resulting spanner.

5.2 Spanners with O(n1−1/d )-separator

Let P be a set of n points in Rd , and let ε > 0 be a parameter. We next describe a modified construction
of SSPDs given in Section 3 for the point-set P, such that when converting it into a spanner, it has a
small separator.

5.2.1 SSPD and WSPD for mildly separated sets

Lemma 5.2. Let P = Pin ∪ Pout be a set of n points in
Rd , p a point, and r, $, R numbers, such that the
following holds (i) there is a ring R = ring p, r, r + $ that separates Pin from Pout , (ii) Pin ⊆ b(p, r),
and (iii) Pout ⊆ b(p, R)\b(p, r + $). Then, for ε > 0, one can compute 1/ε-WSPD W covering Pin ⊗Pout ,
such that:   
(A) There are O ε−2d (r/t)d−1 + log(R/ε$) pairs in W.
(B) Every point participates in O ε−d lg(R/ε$)
pairs in W.

(C) The total weight of W is O nε−d lg(R/ε$) .

(D) The time to compute W is O nε−d lg(R/ε$) .

Proof: Snap the point set P = Pin ∪ Pout to a grid with sidelength ε$/8d, and let S denote the resulting
point set. The set S has spread Φ = O(R/ε$). Use the algorithm of Lemma 2.8 to compute a 4/ε-WSPD
for S. Now, interpret this WSPD as being on the original point set, and use Lemma 2.5 to convert it
into a WSPD covering only Pin ⊗ Pout . Clearly, this is the required 1/ε-WSPD W covering Pin ⊗ Pout .
The running time of the algorithm is O(nε−d log Φ).
We need to bound the number of pairs generated, and their total weight. So, consider the quadtree
used in computing the WSPD for S. Its root has diameter ∆0 ≤ 2dR, and a node in the ith level of the
quadtree has diameter at most ∆i = ∆0 /2i .
We will refer to a pair of the WSPD computed for S that induces at least one non-empty pair in W
as active. Now, a node u of level i in distance ` from the ring, can not participate in an active pair {u, v}
if ` > c∆i /ε, for a sufficiently large constant c, since the parents of u and v are already well-separated,
and S(u) ∪ S(v) contain points from (the snapped
version of) both Pin and Pout . Observe that a sphere
of radius ρ, can intersect at most O (ρ/∆
i)
d−1
cells of a grid of sidelength ∆i . Since for

a, b > 0, we
have that (a + b) d−1
≤2 d−1
a d−1
+b d−1
, we conclude that ring p, r − c∆i /ε, r + c∆i /ε intersects at
most  d−1 !  d−1 !
r + ∆i /ε c∆i /ε 1 r 1
O =O + d
∆i ∆i ε ∆i ε

13
nodes of level i that are active (i.e., participate in pairs of W). The bottom level of the quadtree that
has active pairs is (at most) h = dlg2 (2Rd/ε$)e, and summing over all levels, we have that the number
of active nodes overall is
h  d−1 !    
X 1 r 1 1 r d−1 log R/ε$
N= O + d =O +
i=0
ε ∆i ε ε ε$ εd
   
1 r d−1 R
=O d + log .
ε $ ε$

The total number of pairs generated is O N/εd since every node participates in O 1/εd pairs. Every

point participates in K = O(h/εd ) =
O ε−d log(R/ε$) pairs, and the total weight of the generated

WSPD is O(nK) = O nε−d log(R/ε$) .

Lemma 5.3. Given a point set P = Pin ∪ Pout , and a α-WSPD W covering Pin ⊗ Pout , such that W
has N pairs, it is of total weight W , and every point of P participates in at most T pairs, then one
can convert it into a αε-SSPD with O(N/εd ) pairs, and of total weight O(W/εd ), such that every point
participates in O(T /εd ) pairs.

Proof: Given a pair {X, Y } ∈ W, split X into m = O(1/εd ) clusters X1 , . . . , Xm , each with diameter
≤ εdiam(X) /4. Clearly, each such cluster Xi is αε-semi-separated from Y . Now, replacing {X, Y } by
the semi-separated pairs {X1 , Y } , . . . , {Xm , Y }, and repeating this for all pairs in W, yields the required
SSPD.

Applying Lemma 5.2, with constant separation, and then refining it using the above lemma, implies
the following.
Lemma 5.4. Let P = Pin ∪ Pout be a set of n points in
Rd , p a point, and r, $, R numbers, such that the
following holds (i) there is a ring R = ring p, r, r + $ that separates Pin from Pout , (ii) Pin ⊆ b(p, r),
and (iii) Pout ⊆ b(p, R)\b(p, r + $). Then, for ε > 0, one can compute 1/ε-SSPD W covering Pin ⊗Pout ,
such that:   
(A) There are O ε (r/$)
−d d−1
+ log(R/$) pairs in W.
(B) Every point participates in O ε lg(R/$)
pairs in W.
−d

(C) The total weight of W is O nε−d lg(R/$) .

(D) The time to compute W is O nε−d lg(R/$) .

5.2.2 The SSPD construction

Compute a
ball b(p, r), using Lemma 2.7, with t = (1/2)n1/d . Let r0 = (1 + 1/t)r. We have that
ring p, r, r0 contains at most n1−1/d points of P. We partition P as follows:

Pring = P ∩ ring p, r, r0 ,


Pin = P ∩ b(p, r) ,
Pout = P ∩ ring p, r0 , 2r , and


Pouter = P \ b(p, 2r) .

We have that |Pin | ≥ n/c, |Pring | ≤ n1−1/d , and |Pouter | ≥ n/2 where c is a constant that depends only
on the dimension d. We add the following pairs to the SSPD S.
(A) Pring ⊗ (P \ Pring ): We compute a (1/ε)-SSPD for P using Theorem 4.10, and we split it using
Lemma 2.5 to get a (1/ε)-SSPD for Pring ⊗ (P \ Pring ) (with the same parameters as the original
SSPD of Theorem 4.10).

14
(B) Pin ⊗ Pouter : We decompose Pin into O(1/εd ) clusters each with diameter εr/10 (for example, by
using a grid of the appropriate size). Let F be the resulting set of subsets of Pin . For each X ∈ F,
we add {X, Pouter } as a (1/ε)-semi-separated pair to S.
(C) Pin ⊗ Pout : Compute a O(1/ε)-SSPD for Pin ⊗ Pout using the algorithm of Lemma 5.4. The diameter
of Pin ⊗ Pout is 4r,

and the ring thickness separating Pin from Pout is r/t. The resulting SSPD has
O ε−d td−1 + log t = O ε−d n1−1/d pairs, any point participates in at most O(ε−d log n) pairs,

and the total weight of the SSPD is O(nε−d log n).

(D) Pin ⊗ Pin , Pring ⊗ Pring and (Pout ∪ Pouter ) ⊗ (Pout ∪ Pouter ): We construct the SSPD
S for these two sets
of pairs by recursively calling the algorithm on the sets Pin , Pring and on Pout Pouter .
Lemma 5.5. For a point-set P of n points in Rd , and a parameter ε, the (1/ε)-SSPD generated by the
above construction has: (i) O n/ε pairs,
(ii) every point is contained in O ε log
−d 2
n pairs, (iii) the
d

total weight of the SSPD is O nε log n , and (iv) the construction time is O(nε log2 n).
−d 2 −d

Proof: (i) Let T (n) denote the number of pairs generated by the above algorithm for a set of n points.
We bound the number of pairs generated in each stage separately:
(A) For Pring ⊗ (P \ Pring ), observe that every point participates in at most O(ε−d log n) pairs, and
there are O(n 1−1/d

) points in Pring . As such, the number of pairs generated in this step is
/ε log n , as every pair must involve at least one point of
Pring . Namely, the total
1−1/d d


O n
number of pairs generated for Pring ⊗ (P \ Pring ) is O n /ε log n .
1−1/d d

(B) Separating Pin ⊗ Pouter requires O(1/ε ) pairs.

d

(C) Separating Pin ⊗ Pout requires O ε−d n1−1/d pairs.

(D) Separating Pin ⊗ Pin , Pring ⊗ Pring and (Pout ∪ Pouter ) ⊗ (Pout ∪ Pouter ) requires T (|Pin |), T (|Pring |)
and T (|Pout ∪ Pouter |) pairs, respectively.
As such, we have that
T (n) = O n1−1/d /εd log n + T (|Pin |) + T (|Pring |) + T (|Pout ∪ Pouter |) .

The solution to this recurrence is O n/εd .

(ii) We have that a point participates in at most



D(n) = O(ε−d log n) + O(ε−d log(n/ε)) + max D |Pin | , D |Pring | , D |Pout ∪ Pouter |



 
−d
= O(ε log n) + D (1 − 1/c)n ,

as ε ≥ 1/n, |Pin | ≤ n/2, |Pring
| ≤ n1−1/d , and |Pout ∪ Pouter | ≤ n − |Pin | ≤ (1 − 1/c)n. The solution to
this recurrence is O ε−d log2 n .
(iii) By the above, the total weight of the SSPD generated is O nε−d log2 n .

(iv) As for the construction time, we get R(n) = O nε−d log n + R(n1 ) + R(n2 ) + R(n3 ), where n1 +

n2 + n3 ≤ n and n1 , n2 , n3 ≤ (1 − 1/c)n for some absolute constant c > 1. As such, the construction
time is O(nε−d log2 n).

5.2.3 Converting into spanner

We plug the above SSPD construction into Theorem 5.1 to get a spanner. We remind the reader that the
construction uses a cone decomposition around the smaller part of each pair in the SSPD and connects
the apex of the cone to the
closest point in the other side of the pair inside the cone, as such every SSPD
pair give rise to O 1/εd−1 edges, which all share a single vertex called the hub of the pair. Let G be
the resulting spanner.

15
Lemma 5.6. The graph G has a separator of size O n1−1/d /εd .

Proof: If we remove all the points of Pring , the graph G is almost disconnected. Indeed, removing
all O(n1−1/d ) points of Pring immediately kills all the edges of the spanner that rise out of stage (A).
Stage (B) gives rise to O(1/εd ) pairs and consequently O(1/ε2d−1 ) edges. Eliminating the O(1/εd )
hub vertices eliminates
all such edges. Stage (C) gives rise to O(n /ε ) pairs, which in turn in-
1−1/d d

duces O n 1−1/d 2d−1

/ε edges in the spanner. Again, removing the corresponding O(n1−1/d /εd ) hub
vertices eliminates all such edges. Therefore the set X , of all these O(n1−1/d /εd ) removed vertices, is an
O(n1−1/d /εd )-separator for graph G as it separates Pin from Pout ∪ Pouter .

Theorem 5.7. For any ε > 0 and any set P of n points
in Rd , there is a (1 + ε)-spanner G with
(i) O(n/ε2d−1 ) edges, (ii) maximum degree O (1/ε2d−1 ) log2
n , and (iii) a separator of size O(n1−1/d /εd ).
The (1 + ε)-spanner can be constructed in O (n/εd ) log2 n time.

Proof: Computing the SSPD takes O (n/εd ) log2 n time, and this also bounds the total weight of the

SSPD. Theorem 5.1 converts this into the desired spanner in time proportional to the total weight of
the SSPD.

Theorem 5.7 compares favorably with the result of Fürer and Kasiviswanathan [FK07]. Indeed, the
stated running time of their algorithm is O n (ignoring polylog factors and the dependency
2−2/(dd/2e+1)

on ε). It is quite plausible that their algorithm can be made to be faster (most likely O(n logd−1 n)) for
the special case of the complete graph. However, in the worst case, the maximum degree of a vertex in
their spanner is Ω(n), while in our construction the maximum degree is O(log2 n).

Remark 5.8. Consider the point set made out of the standard n1/d × n1/d × · · · × n1/d grid. For any ε < 1,
all the edges of the grid
must be in the spanner of this graph. However, any separator for such a grid
graph requires Ω n1−1/d vertices [RH01]. Namely, the bound of Theorem 5.7 is close to optimal in the
worst case.

6 Conclusions
We presented several new constructions of SSPDs that have several additional properties that previous
constructions did not have. Our basic construction relied on finding a good ring separator in low
dimension, an idea that should have other applications. To get an optimal construction we used a
random partition scheme which might be of independent interest.
Many of the applications of SSPDs uses cones and angles. It would be interesting to extend some
of these applications to spaces with low doubling dimension. In particular, can one construct a spanner
for a point set, with low degree and a small separator, in a low-doubling-dimension space?

Acknowledgments.
The authors thank Sylvie Temme and Jan Vahrenhold for pointing out mistakes in earlier versions of
this paper. The authors also thank the anonymous referees for their detailed and insightful comments.

16
References
[ACFS09] M. A. Abam, P. Carmi, M. Farshi, and M. H. M. Smid. On the power of the semi-separated
pair decomposition. In Proc. 11th Workshop Algorithms Data Struct., pages 1–12, 2009.

[AdBF+ 11] M. A. Abam, M. de Berg, M. Farshi, J. Gudmundsson, and M. H. M. Smid. Geometric

spanners for weighted point sets. Algorithmica, 61(1):207–225, 2011.

[AdBFG09] M. A. Abam, M. de Berg, M. Farshi, and J. Gudmundsson. Region-fault tolerant geometric

spanners. Discrete Comput. Geom., 41(4):556–582, 2009.

[AH10] M. A. Abam and S. Har-Peled. New constructions of SSPDs and their applications. In
Proc. 26th Annu. ACM Sympos. Comput. Geom., pages 192–200, 2010. http://www.cs.
uiuc.edu/~sariel/papers/09/sspd/.

[Ass83] P. Assouad. Plongements lipschitziens dans Rn . Bull. Soc. Math. France, 111(4):429–448,
1983.

[BS07] B. Bollobás and A. Scott. On separating systems. Eur. J. Comb., 28(4):1068–1071, 2007.

[CK95] P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with

applications to k-nearest-neighbors and n-body potential fields. J. Assoc. Comput. Mach.,
42:67–90, 1995.

[DGK01] C. A. Duncan, M. T. Goodrich, and S. Kobourov. Balanced aspect ratio trees: combining
the advantages of k-d trees and octrees. J. Algorithms, 38:303–333, 2001.

[FK07] M. Fürer and S. P. Kasiviswanathan. Spanners for geometric intersection graphs. In Proc.
10th Workshop Algorithms Data Struct., pages 312–324, 2007.

[FMS03] S. Funke, D. Matijevic, and P. Sanders. Approximating energy efficient paths in wireless
multi-hop networks. In Proc. 11th Annu. European Sympos. Algorithms, pages 230–241,
2003.

[GKL03] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion
embeddings. In Proc. 44th Annu. IEEE Sympos. Found. Comput. Sci., pages 534–543, 2003.

[Har01] S. Har-Peled. A practical approach for computing the diameter of a point-set. In Proc. 17th
Annu. ACM Sympos. Comput. Geom., pages 177–186, 2001.

[Hei01] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New

York, 2001.

[HM06] S. Har-Peled and M. Mendel. Fast construction of nets in low dimensional metrics, and
their applications. SIAM J. Comput., 35(5):1148–1184, 2006.

[KG92] M. J. Keil and C. A. Gutwin. Classes of graphs which approximate the complete euclidean
graph. Discrete Comput. Geom., 7:13–28, 1992.

[LT80] R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J.

Comput., 9(3):615–627, 1980.

17
[MR95] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

[MTTV97] G. L. Miller, S. H. Teng, W. P. Thurston, and S. A. Vavasis. Separators for sphere-packings

and nearest neighbor graphs. J. Assoc. Comput. Mach., 44(1):1–29, 1997.

[NS07] G. Narasimhan and M. Smid. Geometric spanner networks. Cambridge University Press,
2007.

[RH01] A. L. Rosenberg and L. S. Heath. Graph separators, with applications. Kluwer Academic
Publishers, Norwell, MA, USA, 2001.

[SW98] W. D. Smith and N. C. Wormald. Geometric separator theorems and applications. In Proc.
39th Annu. IEEE Sympos. Found. Comput. Sci., pages 232–243, 1998.

[Var98] K. R. Varadarajan. A divide-and-conquer algorithm for min-cost perfect matching in the

plane. In Proc. 39th Annu. IEEE Sympos. Found. Comput. Sci., pages 320–331, 1998.

A Converting a SSPD into a spanner

Abam et al. [AdBFG09] showed how to construct a (1 + ε)-spanner from their SSPD for a set of n points
in a plane. The proof that the resulting graph is (1 + ε)-spanner depends on the SSPD construction,
namely the monotonicity property of the SSPD—see [AdBFG09] for the definition and details. Our
spanner construction from a SSPD S of a set P ⊆ Rd of n points, as describe next, is just a simple
generalization of the construction given in [AdBFG09] but the proof is independent of the construction.

A.1 The construction

For a parameter ψ, we define a ψ-cone to be the intersection of d non-parallel half-spaces such that
the angle of any two rays emanating at the cone’s apex and being inside the cone is at most ψ. Let C
be a collection of O(1/ψ d−1 ) interior-disjoint ψ-cones, each with their apex at the origin, that together
cover Rd . We can construct this collection of cones by a grid induced by a system of halfspaces, such
that given a direction, we can find the cone containing this direction in constant time.
We call the cones in C canonical cones. For a cone σ ∈ C and a point p ∈ Rd , let σ(p) denote the
translated copy of σ whose apex coincides with p.

A.1.1 The spanner construction

We are given a 1/ρ-SSPD S of a point-set P in Rd , where ρ ≤ ε/8. We next show how to convert this
SSPD into a (1 + ε)-spanner of P.
Let ψ = ε/40. We build a graph G having P as its vertex set. Initially the graph has no edges.
Next, for each pair {X , Y} ∈ S pick an arbitrary point p from the set with smaller diameter, say X . We
will refer to p as the hub of X , denoted by hub(X). For each cone σ ∈ C, we connect p to its nearest
neighbor in Y ∩ σ(p) (denoted by q); that is, we insert the edge pq into G, with kpqk as its weight. Thus,
every pair of S contributes |C| edges to G.
We claim that G is the desired spanner.

18
A.2 Analysis
Restatement of Theorem 5.1 Given a 8/ε-SSPD S for a point-set P in Rd , one can compute a
(1 + ε)-spanner of P with O(|S| /εd−1 ) edges. The construction time is proportional to
the total weight
of S. In particular, a point appearing in k pairs of the SSPD is of degree O k/εd−1 in the resulting
spanner.

Proof: The construction is described above (using ρ = ε/8 and ψ = ε/40), and the bound on the number
of edges in the spanner follows immediately.
The proof of the spanner property   is by induction. Sort the pairs of points in P by their length and
n
let p1 q1 , . . . , pu qu be these u = sorted pairs (in increasing order), where n = |P|.
2
It is easy to verify that p1 q1 must be in the spanner. Assume it holds that dG (pi , qi ) ≤ (1 + ε) kpi qi k,
for all i ≤ k. We now prove the claim holds for st, where s = pk+1 and t = qk+1 .
Assume s ∈ Xj and t ∈ Yj for some pair {Xj , Yj } of S. Furthermore,
t
assume that Xj is the set with the smaller diameter, and let p = hub(Xj ). Let
q be the closest neighbor to p inside the cone containing t. By construction, q
the edge pq is in the spanner.
Since s, p ∈ Xj , and t ∈ Yj it follows that kspk < kstk. As such, by s
induction, we have that dG (s, p) ≤ (1 + ε) kspk. It is also easy to verify that
kqtk < kstk (this also follows from the calculations below), which implies that Xj p
dG (q, t) ≤ (1 + ε) kqtk. As such, we have that

E = dG (s, t) − kstk ≤ (1 + ε) kspk + kpqk + (1 + ε) kqtk − kstk

∆=
z }| {
≤ 2 kspk + kpqk + (1 + ε) kqtk − kptk + kspk ≤ 3 kspk + kpqk + (1 + ε) kqtk − kptk .

Let z be the projection of q on the segment pt. It holds kptk = kpzk + kztk. Let t
sin α z
α = ∠tpq ≤ ψ. Now, observe that tan α = ≤ 2ψ, because sin α ≤ α ≤ ψ, and
cos α α
cos α ≥ cos ψ ≥ 1/2, since ψ ≤ π/3. As such kzqk = kpzk tan α ≤ 2ψ kpzk. This
p q
implies that

∆ = kpqk + (1 + ε) kqtk − kptk ≤ kpzk + kzqk + (1 + ε)(kzqk + kztk) − kpzk − kztk

≤ (2 + ε) kzqk + ε kztk ≤ 2ψ(2 + ε) kpzk + ε kztk ≤ 6ψ kpzk + ε kztk
≤ (6ψ − ε) kpzk + ε(kpzk + kztk) = (6ψ − ε) kpzk + ε kptk .

Now, by the above kpzk ≤ kpqk and kspk ≤ (ε/8) kpqk. As such,

E ≤ 3 kspk + ∆ ≤ 3 kspk + (6ψ − ε) kpzk + ε(kspk + kstk)

ε
≤ 4 kspk + (6ψ − ε) kpzk + ε kstk ≤ kpqk + (6ψ − ε) kpqk + ε kstk
2
 ε
= 6ψ − kpqk + ε kstk ≤ ε kstk ,
2
since ψ ≤ ε/12 implies that 6ψ − 2ε ≤ 0. This implies that dG (s, t) ≤ (1 + ε) kstk.

19
Construction time. To implement this construction we scan the pairs of the SSPD one by one. For
each such pair {X , Y}, we do the following.
First, we need to determine if diam(X ) = O(diam(Y)) or diam(Y) = O(diam(X )) (so we known
which set is roughly smaller). This can be done in O(|X | + |Y|) by approximating the diameter of both
sets in linear time. Next, for each such pair (assume X has a smaller diameter than Y), we need to find
the nearest neighbor to hub(X ) in Y, in each one of the cones. To this end, we have a grid of directions
around hub(X ), and we compute for each grid cell all the points of Y falling into this cell. Next, for all
the points in such a grid cell, we find the closest point to hub(X ) in linear time.
This takes O(|X | + |Y|) time for the pair {X, Y }. Overall, this takes time linear in the total weight
of the given SSPD.

B Lower bound for SSPD constructed using BAR trees

Here, we demonstrate that a point might participate in a linear number of pairs in the SSPD if one uses
the previous construction of Abam et al. [AdBFG09].

Theorem B.1. There is a configuration of n points in the plane, such that a point appearing in n − 1
pairs of the SSPD constructed using the algorithm of Abam et al. [AdBFG09].

Proof: For the sake of simplicity of exposition, we assume that n is a power of 2.

Consider the configuration illustrated in the figure on the right, where Rq,r
n − 2 points are on a line making a 135-degree angle with the x-axis, and the q
two other points q and r are far from them. Let P denote this set of points.
The BAR-tree construction algorithm [DGK01], used on P, first separates
the points q and r from the rest of the points by a 135-degree splitting line
r
`. This splitting line produces two fat regions. One region, denoted by Rq,r ,
contains q and r, and the other region, denoted by Rrest , contains the rest
of the points. The diameter of points inside Rq,r is kqrk, and it is large Rrest
`
compared to the diameter of points inside Rrest or any subsequent subcell
created inside Rrest .
Now, a node v (and its corresponding region) of a BAR tree is of weight class i, if |Pv | ≤ n/2i
and Pp(v) > n/2i . As such, the region Rq,r appears in all the weight classes for i = 1, · · · , lg n − 1, see
[AdBFG09]. The algorithm of Abam et al. [AdBFG09] creates pairs only between nodes that belong to
the same weight class (a node might belong to several weight classes).
Observe that by placing the points of Rrest sufficiently close to the splitting line `, one can guarantee
that any boundary of a subcell of Rrest in the BAR-tree intersects `. Namely, no subcell of Rrest can
be semi-separated from Rq,r , unless it contains a single point of P (and then its diameter is treated as
being zero). Therefore, semi-separated pairs involving q and r that are produced in the weight class
i = 1, · · · , lg n − 1 are of the form ({q, r}, {z}) where z ∈ P \ {q, r}. Moreover, sets involved in the
produced semi-separated pairs in the weight class lg n are singletons. Therefore, both q and r appear
in n − 2 pairs which all together semi-separate {q, r} from P \ {q, r}. Since the algorithm also generates
the pair {{q} , {r}}, these two points participate in n − 1 pairs.

20