# Why is the Gromov-Hausdorff distance a metric?

The Gromov-Hausdorff distance is: $$d_{GH}(A,B) = \inf_{f,g}d_H(A',B')$$where $f$ and $g$ are isometric embeddings of $A,B$ into some metric space, and their images are $A', B'$. The inf is taken over all embeddings.

My problem with this is that I don't see a reason the triangle inequality should hold here.

$$d_{GH}(A,B) \leq d_{GH}(A,C) + d_{GH}(C,B)$$

My problem is that the embeddings change and I don't really see what I can work with here. Any help would be welcomed!

• How is defined $d_H$? – ajotatxe Jul 24 '15 at 17:18
• Sorry, I forgot to say that that is the Hausdorff distance. – John H. Jul 24 '15 at 17:19
• Hint: Paste together two embeddings along their respective copies of $C$. – Jim Belk Jul 24 '15 at 17:53

Although the definition of GH metric mentions embeddings into an arbitrary metric space $X$, we can always truncate $X$ to the union of the image of $A$ and the image of $B$. In other words, it suffices to consider semimetrics on the abstract disjoint union $A\sqcup B$ that are compatible with the given metrics on $A$ and $B$. (Semimetrics are allowed to take value $0$; this is because the images of $A$ and $B$ under an embedding into $X$ could overlap.) The GH distance is the infimum of the Hausdorff distance between $A$ and $B$ with respect to all compatible semimetrics.
Given a compatible semimetric $\rho_1$ on $A\sqcup B$ and a compatible semimetric $\rho_2$ on $B\sqcup C$, define a compatible semimetric $\rho$ on $A\sqcup C$ so that $$\rho(a,c) = \inf_{b\in B}(\rho_1(a,b)+\rho_2(b,c)),\quad a\in A, \ c\in C$$
It remains to check the triangle inequality, which is easier to do yourself than to read someone else's demonstration... Say, we have $a,a'\in A$ and $c\in C$: pick $b$ and $b'$ that realize $\rho(a,c)$ and $\rho(a',c)$ within $\epsilon$. Then $$\begin{split}\rho(a,c) &\le \rho_1(a,b)+\rho_2(b,c) \\&\le \rho_1(a,b')+\rho_2(b',c) +\epsilon \\& \le \rho_1(a,a')+\rho_1(a',b') +\rho(b',c) +\epsilon \\& \le \rho_1(a,a')+\rho(a',c )+2\epsilon\end{split}$$ Similarly for other cases.