In the Geometric Spanner Networks book by Giri Narasimhan and Michiel Smid Page 153 says

Definition 9.1.3 (Well-Separated Pair Decomposition). Let $S$ be a set of $n$ points in $\mathbb R^d$, and let $s > 0$ be a real number. A well-separated pair decomposition (WSPD) for $S$, with respect to $s$, is a sequence

$\{A_1, B_1\},\{A_2, B_2\}, \cdots , \{A_m, B_m\}$

of pairs of nonempty subsets of $S$, for some integer $m$, such that

  1. for each $i$ with $1 \leq i \leq m, A_i$ and $B_i$ are well-separated with respect to $s$, and
  2. for any two distinct points $p$ and $q$ of $S$, there is exactly one index $i$ with $1 \leq i \leq m$, such that
    • $p \in A_i$ and $q \in B_i$ or
    • $p \in B_i$ and $q \in A_i$

Look at the following image

enter image description here

The points $x_1, x_2, x_3$ are given in the plane and the split tree is drawn. Suppose for some $s$ the WSPD is built as shown. In this way the well separated pairs are going to be

$ A_1 = \{x_1, x_2\}, B_1 = \{x_3 \} $

$ A_2 = \{x_1\}, B_2 = \{x_2 \} $

The $x_1,x_2$ together are well separated to $x_3$ and $x_1$ is well separated to $x_2$. As you see $x_1 \in A_1$ and $x_1 \in A_2$, so it is in more than one pair which contradicts the definition.

I would like to know what is the problem with my example and why every point is in exactly one pair in Well Separated Pair Decomposition?

Thanks in advance.


1 Answer 1


OK, I found it. The definition says

for any two distinct points ...

It means I must consider two points, not a one solitary. $x_1$ is well separated with $x_3$, and it is well separated with $x_2$ as well, But there is exactly one pair that separates $x_3$ from $x_1$ and also there is exactly one pair that separates $x_2$ from $x_1$

  • $\begingroup$ Self answer is ok, if you found something that may be confusing, solved it later and moreover the question is on-topic and references are proper (everything is fine) then you should accept your answer to indicate the problem is resolved. Thank you. $\endgroup$
    – Evil
    Commented Nov 25, 2017 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.