2
$\begingroup$

Similar questions have been asked here and here.

Let $\mathbb{H}(X)$ denote the set of all nonempty compact subsets of $X$, where $(X, d)$ is a metric space.

Define the Hausdorff Distance as

$d_{\mathbb{H}}(A, B):=$max$\{\underset{a\in A}\sup d(a, B), \underset{b\in B}\sup d(b, A)\}$, where $d(a, B):=\inf\{d(a, b): b\in B\}$ and $d(b, A):=\inf\{d(b, a): a\in A\}$.

My question:

Is there a way to prove the Triangle Inequality without using the identity $d_{\mathbb{H}}(A, B)=\inf\{\epsilon\geq 0: A\subset B_{\epsilon}, B\subset A_{\epsilon}\}$, where $A_{\epsilon}:=\underset{a\in A}\bigcup\{x\in X: d(x, a)\leq\epsilon\}$?

Many thanks in advance!

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes, you can:

Define (for convenience's sake) $$ \rho(A,B) = \sup_{a \in A} d(a,B) \text{ and } \rho(B,A) = \sup_{b \in B} d(b,A)$$

so that $$=d_H(A,B)=\max(\rho(A,B),\rho(B,A))$$

I claim that for $\rho$ we also have a triangle inequality:

$$\rho(A,B) \le \rho(A,C) + \rho(C,B)\tag{0}$$ for compact, non-empty $A,B,C \subseteq X$.

To see that: let $a \in A$ be arbitrary. By compactness of $C$, there is some $c_a \in C$ so that $d(a,c_a)=d(a,C)$. Then: $$d(a,B)= \inf_{b \in B} d(a,b) \le \inf_{b \in B} \left(d(a,c_a) + d(c_a,b)\right)$$ by the standard triangle inequality for $d$ ($a$ to $b$ via $c_a$). The left summand does not depend on $b$ so continuing the previous:

$$\inf_{b \in B} \left(d(a,c_a) + d(c_a,b)\right) = d(a,c_a) + \inf_{ \in B} d(c_a,B) = d(a,C) + d(c_a,B) \le \rho(A,C) + \rho(C,B)$$ by the definition, choice of $c_a$ and using that the $\rho$ is a sup, so upperbound. The right hand side is a fixed number which is an upperbound for $d(a,B)$, while $a\in A$ was arbitrary, so $(0)$ follows, as the sup is is the smallest upperbound.

Now the triangle inequality for $d_H$ is an easy consequence, using $x \le \max(x,y)$ etc: first note

$$\rho(A,B) \le \rho(A,C) + \rho(C,B) \le d_H(A,C) + d_H(C,B)\tag{a}$$ and then

$$\rho(B,A) \le \rho(B,C) + \rho(C,A) \le d_H(C,B) + d_H(C,A)\tag{b}$$

The right hand sides of $(a)$ and $(b)$ are identical by symmetry of $d_H$, and as both $\rho(A,B)$ and $\rho(B,A)$ are upper-bounded by it, so is their maximum, so

$$d_H(A,B) \le d_H(A,C) + d_H(C,B)$$ as required. QED.

$\endgroup$
2
  • $\begingroup$ I believe "$d(a,B)= \inf_{b \in B} d(a,b) = \inf_{b \in B} \left(d(a,c_a) + d(c_a,b)\right)$" should be "$d(a,B)= \inf_{b \in B} d(a,b) \leq \inf_{b \in B} \left(d(a,c_a) + d(c_a,b)\right)$" instead; but other than that-thank you so much! $\endgroup$ Commented Feb 24, 2022 at 14:39
  • 1
    $\begingroup$ @DickGrayson quite right… $\endgroup$ Commented Feb 24, 2022 at 15:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .