Distance between sets (a triangle-type inequality)

  • Thread starter Identity
  • Start date
  • #1
152
0

Main Question or Discussion Point

I've been reading a book called Superfractals, and I'm having trouble with a particular proof:

Definitions:

The distance from a point [itex]x \in X[/itex] to a set [itex]B \in \mathbb{H}(X)[/itex] (where [itex]\mathbb{H}(X)[/itex] is the space of nonempty compact subsets of [itex]X[/itex] is:
[tex]D_B(x):=\mbox{min}\lbrace d(x,b):b \in B\rbrace[/tex]
The distance from [itex]A \in \mathbb{H}(X)[/itex] to [itex]B \in \mathbb{H}(X)[/itex] is:
[tex]D_B(A):=\mbox{max}\lbrace D_B(a):a \in A\rbrace[/tex]
for all [itex]A,B \in \mathbb{H}(X)[/itex].
The proof is to show that [itex]D_B(A) \leq D_B(C)+D_C(A)[/itex]. The proof goes:
[tex]\begin{array}{rcl}D_B(a) &=&\mbox{min}_{b \in B}d(a,b) \\
&\leq& \mbox{min}_{b \in B}(d(a,c)+d(c,b))\\
&=&d(a,c)+\mbox{min}_{b \in B}d(c,b)\\
\end{array}[/tex]
Then
[tex]D_B(a) \leq \mbox{min}_{c \in C}d(a,c)+\mbox{max}_{c \in C}\mbox{min}_{b \in B}d(c,b)[/tex]

How do we reach this last step?
 

Answers and Replies

  • #2
22,097
3,279
I've been reading a book called Superfractals, and I'm having trouble with a particular proof:

Definitions:

The distance from a point [itex]x \in X[/itex] to a set [itex]B \in \mathbb{H}(X)[/itex] (where [itex]\mathbb{H}(X)[/itex] is the space of nonempty compact subsets of [itex]X[/itex] is:
[tex]D_B(x):=\mbox{min}\lbrace d(x,b):b \in B\rbrace[/tex]
The distance from [itex]A \in \mathbb{H}(X)[/itex] to [itex]B \in \mathbb{H}(X)[/itex] is:
[tex]D_B(A):=\mbox{max}\lbrace D_B(a):a \in A\rbrace[/tex]
for all [itex]A,B \in \mathbb{H}(X)[/itex].
The proof is to show that [itex]D_B(A) \leq D_B(C)+D_C(A)[/itex]. The proof goes:
[tex]\begin{array}{rcl}D_B(a) &=&\mbox{min}_{b \in B}d(a,b) \\
&\leq& \mbox{min}_{b \in B}(d(a,c)+d(c,b))\\
&=&d(a,c)+\mbox{min}_{b \in B}d(c,b)\\
\end{array}[/tex]
Then
[tex]D_B(a) \leq \mbox{min}_{c \in C}d(a,c)+\mbox{max}_{c \in C}\mbox{min}_{b \in B}d(c,b)[/tex]

How do we reach this last step?
First of all, we notice that

[tex]\min_{b\in B}~d(c,b) \leq \max_{x\in C}~\min_{b\in B}~d(c,b)[/tex]

So

[tex]D_B(a)\leq d(a,c)+\mbox{min}_{b \in B}d(c,b)\leq d(a,c)+\mbox{max}_{c \in C}\mbox{min}_{b \in B}d(c,b)[/tex]

For notational issues, let [itex]S=\mbox{max}_{c \in C}\mbox{min}_{b \in B}d(c,b)[/itex] this is just a number.

So we have proven that

[tex]D_B(a)\leq d(a,c)+S[/tex]

But this holds for ALL c. So it must also hold for any particular c. So it must also hold for the c that minimizes d(a,c). So

[tex]D_B(a)\leq \min_{c\in C}~d(a,c)+S[/tex]
 
  • #3
152
0
Thnks micromass :)
 

Related Threads on Distance between sets (a triangle-type inequality)

Replies
3
Views
2K
  • Last Post
Replies
1
Views
1K
Replies
5
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
9
Views
5K
  • Last Post
Replies
3
Views
2K
Replies
12
Views
4K
Top