# Prove that the Hausdorff Distance satisfies the Triangle Inequality.

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\}$$?

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.

• 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! Commented Feb 24, 2022 at 14:39
• @DickGrayson quite right… Commented Feb 24, 2022 at 15:07