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!

  • $\begingroup$ How is defined $d_H$? $\endgroup$ – ajotatxe Jul 24 '15 at 17:18
  • $\begingroup$ Sorry, I forgot to say that that is the Hausdorff distance. $\endgroup$ – John H. Jul 24 '15 at 17:19
  • 2
    $\begingroup$ Hint: Paste together two embeddings along their respective copies of $C$. $\endgroup$ – 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.

Related: What is meant by gluing two metric spaces together?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.