# Why every point is in exactly one pair in Well Separated Pair Decomposition(WSPD)

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

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$

• 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. – Evil Nov 25 '17 at 0:31