Give two metric space $X,Y$, we denote by $d_{GH}(X,Y)$ the Gromov- Haudorff distance. It seems that it only relies on $X,Y$ not on the ambient metric space $Z$ where we embed $X,Y$ (because in the notation, there is no $Z$). How can we prove this is well-defined?


$d_{GH}(X, Y)$ is computed by looking at all possible "ambient spaces" $Z$. The phrasings one often sees, like

The infimum over all embeddings of $X, Y$ into a common space $Z$,

can make it sound like there is a "special" $Z$. But rather, we're looking at all pairs of embeddings into all (possible) spaces.

EDIT: Specifically, here's a clearer way to define $d_{GH}(X, Y)$.

$d_{GH}(X, Y)$ is the infimum of the set of $\delta$ such that, for some metric space $Z$ and some embeddings $f, g: X, Y\rightarrow Z$, we have $d_{H}^Z(f(X), g(Y))=\delta$ (where "$d_H^Z$" denotes the usual Hausdorff distance in $Z$).

In particular, we look at all possible embeddings of $X$ and $Y$ into all possible spaces. There is no single $Z$ we're looking at!

Incidentally, it's not hard to prove - and fairly useful - that we can restrict attention to those $Z$s whose underlying set is $X\sqcup Y$ and whose metric restricted to $X$ (resp. $Y$) is just the original $X$-metric (resp. $Y$-metric).

Again, that is:

Theorem. $d_{GH}(X, Y)$ is equal to the infimum of the set of $\epsilon$ such that, for some metric space $Z$ with underlying set $X\sqcup Y$ whose metric on the $X$ part (resp., $Y$ part) is the same as the $X$ metric (resp., $Y$ metric), we have $d_H^Z(X, Y)=\epsilon$.

Note that this is made much clearer if we distinguish between the set $A$ and the metric space $\mathcal{A}=(A,d_A)$. Namely, we have:

Theorem, rephrased. $d_{GH}((X, d_X),(Y, d_Y))$ is equal to the infimum of the set of $\epsilon$ such that, for some metric $d$ on $X\sqcup Y$ with $d\upharpoonright X=d_X$ and $d\upharpoonright Y=d_Y$, we have $\epsilon=d_H^{(X\sqcup Y, d)}(X, Y)$.

Again, though, we're looking at all possible metrics on $X\sqcup Y$ which restrict to $d_X$ and $d_Y$ on $X$ and $Y$, respectively.

  • $\begingroup$ How to define a metric on $X\sqcup Y$? $\endgroup$ – Upc Aug 1 '17 at 20:33
  • $\begingroup$ @XavierYang There's not a single one. We look at all possible metrics on that set which extend the $X$-metric on the $X$-part and the $Y$-metric on the $Y$-part. $\endgroup$ – Noah Schweber Aug 1 '17 at 21:16
  • $\begingroup$ @XavierYang I've edited, hopefully this makes things clearer. The point is that we are always, no matter how we define the Gromov-Hausdorff definition, taking an infimum over lots of different metric spaces; there's no "one metric space $Z$," or "one metric on $X\sqcup Y$," which plays a special role here. $\endgroup$ – Noah Schweber Aug 1 '17 at 21:24
  • $\begingroup$ Thanks, now it is clear, theoretically. But pratically, how can I calculate the GH distance between e.g. $S^1$ and $S^2$ or $S^1$ and $\mathbb{R}$ (of course, all are equipped with usual metric)? $\endgroup$ – Upc Aug 1 '17 at 21:39
  • $\begingroup$ @XavierYang With reasonable spaces, you can often guess the correct answer; the verification, however, is generally not that simple. The power of $d_{GH}$ lies in its applications, not in its ease of calculation. $\endgroup$ – Noah Schweber Aug 1 '17 at 21:44

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.