An introduction to the Gromov-Hausdorff distance

Title: An introduction to the Gromov-Hausdorff distance
Abstract: We give a brief introduction to the Hausdorff and Gromov-Hausdorff distances between metric spaces. The Hausdorff distance is defined on two subsets of a common metric space. The Gromov-Hausdorff distance is defined on any two arbitrary metric spaces. The Gromov-Hausdorff distance gives a metric on all isometry classes of compact metric spaces.
Notes: www.math.colos...

[@sethjchandler]

I appreciate the effort to create a visual explanation of a complex concept. I think it would be better however, at least for those of us not versed in topology, To be a little clearer about what you mean by thickening. I also think that showing the numerical value of epsilon would make the initial example clearer. But, I realize this is a hard concept and that visualization is difficult. Thanks for the effort.

[@aatrn1]

Thanks!

[@bryanbischof4351]

Very clever use of the technology to add intuition. What are good algorithms for approximating Hausdorff dimension? GH seems pretty incomputable considering it’s over all isotopic embeddings.

[@HenryAdamsMath]

Thanks! The Gromov-Hausdorff distance is indeed very hard to compute. See for example the paper link.springer.com/article/10.1007/s00454-017-9889-4 and the references within. That paper shows that GH distances cannot be approximated in polynomial time, for example. Lemma 2.5 of that paper recasts the Gromov-Hausdorff distance in terms of "correspondences", which seem much more computable (no infimum over all pairs of isometric embeddings into some common space), but still the space of all possible correspondences is very large and hard to work with. The Gromov-Hausdorff distance between the n-sphere and the m-sphere is not even known in general; see Example 5.3 link.springer.com/article/10.1007/s00454-012-9406-8 for a lower bound on the Gromov-Hausdorff distance between S^1 and S^2 using "curvature sets". Theorem 5.2 of link.springer.com/article/10.1007/s10711-013-9937-z shows how you can compute persistent homology to get a lower bound on the Gromov-Hausdorff distance. See dl.acm.org/doi/10.1145/3185466 for some results in the setting of metric trees. You may also be interested in mathoverflow.net/questions/23048/what-are-the-tricks-for-computing-estimating-gromov-hausdorff-distance?noredirect=1&lq=1.

[@수학수학-c3h]

@@HenryAdamsMath thanks for the detailed explanation, this is really helpful :)

[@lesliequincosa9554]

Nice intuition, thank you!

[@aatrn1]

Glad it was helpful!

[@ajigao1269]

Thanks for your vivid presentation.
I wonder if there is a mathematical relationship between Hausdorff measure and Hausdorff distance? I Intuitively thought that Hausdorff distance is the difference of two sets's Hausdorff measure, but I can‘t find the mathematical evidence. And where I can find more information about the derivation of Hausdorff distance?

[@HenryAdamsMath]

Hi Aji, great questions. I personally don't think of the Hausdorff measure and the Hausdorff distance as being directly connected, but I have no doubt that others do think of them as being connected, and that relationships between the two arise! For a few other references on the Hausdorff distance, see for example
en.wikipedia.org/wiki/Hausdorff_distance (and the references within)
web.stanford.edu/class/cs273/scribing/2004/class8/scribe8.pdf
www2.math.upenn.edu/~brweber/Lectures/USTC2011/Lecture%205%20-%20Gromov-Hausdorff%20distance.pdf
www.lpsm.paris/pageperso/aamari/teaching/2019-2020/M2_Jussieu/Lesson%202.pdf
www.sciencedirect.com/topics/computer-science/hausdorff-distance

[@Zane3G]

In general relationships between measure and hausdorff distance are difficult considering that finite spaces approximate compact spaces arbitrarily well.
To achieve a meaningful relationship you need a finitistic notion of measure such as covering number or packing number

[@inothernews]

Thanks for the wonderful content. The clarity encourages viewers to further read more into the subject. Would love to see more!
I'm not so familiar with isometric embeddings, so I have some questions!
1. Will there always be a common Z into which X and Y may isometrically embed?
2. If there is such a Z, does it mean GH(X,Y)

[@HenryAdamsMath]

Thanks, I really appreciate it! I'll be teaching a 2-credit 8-week class on applied topology starting soon, so more content will be coming! If you're interested in linear programming, then I have 50 videos from last semester at th-cam.com/play/PLDndWhwv4Ujo10_a2T4R4Uqng1nduvfu1.html. Regarding your questions:
1. Yes! In fact, you can always take Z to be the disjoint union of X and Y, equipped with some metric. This metrc extends the metric on X alone and on Y alone, but there are potentially many ways to define the distance in the disjoint union between a point in X and a point in Y in order to get a metric.
2. Yes! If X and Y live inside the same space W, then d_GH(X,Y)

[@aatrn1]

Hi Andrea, yes, you are exactly right, that is an equivalent definition! And it makes the Gromov-Hausdorff distance sound more computable, doesn't it. Thanks for this good point!

[@virendrak.iitdelhi6458]

Nice explanation.

[@HenryAdamsMath]

Thanks so much!

[@benjaminreames8725]

What’s the software here ?

[@houtarooreki9802]

Thank you sir!

[@aatrn1]

You bet!