Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Distance between sets (a triangle-type inequality)

  1. Nov 26, 2011 #1
    I've been reading a book called Superfractals, and I'm having trouble with a particular proof:


    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)\\
    [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?
  2. jcsd
  3. Nov 27, 2011 #2
    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]


    [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]
  4. Nov 29, 2011 #3
    Thnks micromass :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook