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

Gromov-Hausdorff distance (Wikipedia) between two compact manifolds measures how far away the manifolds are from being isometric. 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. Apr 30, 2010 at 1:42

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}|\operatorname{diam}(X)-\operatorname{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.

Not sure if this is a helpful example but if $$Y$$ is the space of a single point, then

$$d_{GH}(X,Y) \leq \text{rad} \: X = \inf_{y \in X} \sup_{x \in X} d(x,y),$$

which is just the radius of the smallest ball which covers $$X$$.

Also, a sequence of cylinders with any base point such that the radii of the cylinders goes to zero has $$\mathbb{R}$$ as its Gromov-Hausdorff limit.

Can you use an idea the you can learn on the book of Petersen. The idea is that you can use set's $$\epsilon-$$dense, more precisely. If $$X$$ is compact and suppose that we have a finite subset $$A\subset X$$ such that every point in $$X$$ is within distance $$\epsilon$$ of some element in $$A$$, it's easy to see that $$d_{GH}(X,A)<\epsilon$$, more general

Suppose we have $$\epsilon-$$dense subsets

$$A=\{x_1,...,x_k\}\subset X$$ and $$B=\{y_1,..,y_k\}\subset Y$$

with the further property that

$$|d(x_i,x_j)-d(y_i,y_j)|\leq \epsilon$$ for$$1\leq i,j \leq k$$.

Then $$d_{GH}(X,Y)\leq 3\epsilon$$

If you have two spheres, you can prove that the convergence on radius implies the convergence on Gromov-Hausdorff metric, just use that for enough close radius you can take radial projections of $$\epsilon-$$dense subset and you still have this property.