# What are the tricks for computing\estimating Gromov-Hausdorff distance?

Gromov-Hausdorff distance between two compact manifolds measures how far away the manifolds are from being isometric. (Wikipedia: http://en.wikipedia.org/wiki/Gromov%E2%80%93Hausdorff_convergence) In many cases it is possible to do coarse estimates and conclude that a sequence of manifolds converges or diverges.

How does one usually go about calculating GH distance precisely?

Example: Take two spheres of different radii $r$ and $R$ with intrinsic (i.e the distance between two points is the length of the arc of a great circle that connects them) metrics obtained from standard embeddings into $\Bbb R^n$. What is the GH distance between them?

-
I once asked Dima Burago this question, and his response was that (a) there are very few pairs of spaces for which the precise GH distance is known and (b) he could not think of a single reason off the top of his head why one would want to know. As you say, it is mainly useful to know when it is finite and when a sequence of spaces converges. –  Paul Siegel Apr 30 '10 at 1:42
Thank you!_____ –  Zarathustra Apr 30 '10 at 1:49

I misinterpreted the question at first, sorry. Here's my new answer:

First, an answer to the wrong question

For two $(n-1)$ dimensional spheres of radii r and R with the metrics induced from embedding in $\mathbb{R}^n$ (note, this is the "chord metric" not the "round metric" as Zarathustra desired), the Gromov-Hausdorff distance is $|r-R|$. We can achieve this as an upper bound by embedding the two spheres in a concentric fashion, and it's seen to be sharp by the inequality $d_{GH}(X,Y)\geq \frac{1}{2}|diam(X)-diam(Y)|$.

See e.g. Burago Burago and Ivanov, ex. 7.3.14 which is a good source in general.

Now an answer to the correct question

The answer is $\frac{\pi}{2}|R-r|$ for spheres with the round metric, as Anton more or less suggested. This follows easily from the discussion following defn. 7.3.17 in BBI.

Out of laziness, I've written out some of the details here. A "correspondence" of metric spaces $X$ and $Y$ is defined to be a subset $\mathcal{R}$ of $X\times Y$ such that for every point $x\in X$ there is at least one point $(x,z)\in\mathcal{R}$ and for every $y\in Y$ there is at least one point $(w,y)\in\mathcal{R}$. From this one can prove Theorem 7.3.25 which states

$d_{GH}(X,Y)=\frac{1}{2}\inf_{\mathcal{R}}dis\mathcal{R}$

where the infimum is taken over all correspondences $\mathcal{R}$ and $dis\mathcal{R}$ is the distortion of $\mathcal{R}$, defined to be $\sup\{|d_X(x,x')-d_Y(y,y')|:(x,y),(x',y')\in\mathcal{R}\}$.

Take $\mathcal{R}$ to be the correspondence consisting of pairs $(x,y)$ with $x\in S^2_{r}$ and $y\in S^2_{R}$ if $x$ and $y$ lie on the same ray through the origin when the two spheres are embedded in $\mathbb{R}^3$. The distortion of this correspondence is $\pi|R-r|$ by taking $x$ and $x'$ to be antipodal points on one of the spheres. This gives an upper bound for $d_{GH}$ of $\frac{\pi}{2}|R-r|$, and this is sharp again by the inequality above.

A possibly useful reference for G-H distance for subsets of Euclidean space in general

For the rest of your question, you might find interesting a paper by Facundo Mémoli which discusses the case when X and Y are subsets of Euclidean space. See also slides here.

-
jc, thanks for your answer. I think there is a misunderstanding. Probably I was not very clear. The spheres have intrinsic metric. Hence, the diameters are $\pi r$ and $\pi R$. –  Zarathustra Apr 30 '10 at 1:43
@Zarathustra, still from the exercise you get $d_{GH}=\pi(R-r)$. –  Anton Petrunin Apr 30 '10 at 2:21
jc, thank you. Your new proof gives the answer $1/2\pi (R-r)$, not $\pi (R-r)$. –  Zarathustra May 1 '10 at 14:30
Right, silly factors of 1/2. –  j.c. May 1 '10 at 15:23