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

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

Thanks in advance.

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

Thanks in advance.

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

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

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

Thanks in advance.