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!
Best Answer
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.