Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
2 added 4 characters in body

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 thewhat is the problem with my example and why every point is in exactly one pair in Well Separated Pair Decomposition?

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 the is the problem with my example and why every point is in exactly one pair in Well Separated Pair Decomposition?

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?

1

# 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 the is the problem with my example and why every point is in exactly one pair in Well Separated Pair Decomposition?