30
$\begingroup$

The Hausdorff distance between the closed unit disk $D^2$ of $\mathbb R^2$ (equipped with the standard Euclidean distance) and its boundary circle $S^1$ is obviously one.

Interestingly, the Gromov-Hausdorff distance between $D^2$ and $S^1$ is smaller. I claim that it is $\sqrt 3/2$. Below are partial results to support this.

First some notation. A correspondence between two metric spaces $X$ and $Y$ is a subset $R \subset X \times Y$ such that the natural projections of $R$ onto $X$ and $Y$ are both surjective. The distortion of $R$ then is $$ \operatorname{dis}(R) := \sup\{|d_X(x,x')-d_Y(y,y')|\, : \, (x,y), (x',y') \in R\} \ . $$ It can be shown that the Gromov-Hausdorff distance between $X$ and $Y$ is equal to $\frac{1}{2}\inf\operatorname{dis}(R)$, where the infimum is taken over all correspondences between $X$ and $Y$.

Here is a correspondence $R$ between $D^2$ and $S^1$ with distortion $\sqrt 3$. In $R$ are all pairs $(x,x)$ if $x \in S^1$ and also all pairs $(x,c)$ if $c$ is the "center" of the sector to which $x$ belongs as indicated in the following figure ($\sqrt 3$ is the distance between two different black center points):

Below is a sketch of a proof that $\operatorname{dis}(R) \geq \sqrt 3$ in case $R$ is a correspondence between $D^2$ and $S^1$ for which $(x,x) \in R$ for all $x \in S^1$: Color $D^2$ with three colors. First color three arcs of length $2\pi/3$ on $S^1$ with different colors as in the figure above. Now for any $x \in D^2\setminus S^1$ assign to it the color of $y \in S^1$ if $(x,y) \in R$ (pick one in case there are multiple choices). As an application of Sperner's lemma there are three arbitrarily close points of different color. So these three points correspond to points on different arcs of the boundary. This forces $\operatorname{dis}(R) \geq \sqrt 3$. (The assumption $(x,x) \in R$ for $x \in S^1$ is used for the boundary condition in Sperner's lemma.)

Does someone have an idea how to get rid of the condition $(x,x) \in R$ for $x \in S^1$ in the statement above? This would then prove that the Gromov-Hausdorff distance between $D^2$ and $S^1$ is indeed $\sqrt 3/2$.

$\endgroup$
7
$\begingroup$

It seems that there are relations with $\mathrm{dis}(R)<\sqrt3$.

Take a regular heptagon $S_1\dots S_7$ inscribed into the unit circle $S$. Consider a partition into 7 parts $\mathcal P_1,\dots, \mathcal P_7$, and choose the points $A_1,\dots,A_7$ as shown below. Let $M_i$ be the point symmetric to $S_i$. All the numerations are cyclic modulo 7.

The correspondence is defined as follows.

$\bullet$ Every point in $\mathcal P_i$ corresponds to $S_i$.

$\bullet$ $A_i$ corresponds to each point of the arc $M_{i+3}M_{i+4}$.

Partition

In order to show that $\mathrm{dis}(R)<d$ (with $d>S_1S_3$) for this relation, it suffices to do the following.

($\downarrow$) To show that $d(x,x')<d(y,y')+d$:

(1) $\mathrm{diam}(\mathcal P_i)<d$;

(2) $A_iA_{i+1}<d$;

(3) $H(A_i,\mathcal P_{i\pm 1})<d+S_1M_4=d+2\sin\frac\pi{14}$, where $H$ is the Hausdorff distance (i.e., the maximal distance from $A_i$ to a point in $\mathcal P_{i\pm 1}$; in fact, in our case this distance is even $<d$).

($\uparrow$) To show that $d(x,x')>d(y,y')-d$:

(4) $\rho(\mathcal P_i,\mathcal P_{i\pm 3})>2-d$;

(5) $A_iA_j>2-d$;

(6) $\rho(A_i,\mathcal P_{i\pm2})>S_1M_2-d=2\sin\frac{5\pi}{14}-d$.

One can easily check that all these conditions hold for $d=\sqrt3$.

DISCLAIMER. I did not try to optimize this example. Perhaps, it is possible to reach $\mathrm{dis}(R)<1.7$, or even $1.6$, in this way.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice, and unexpected for me :) Have you tried the same idea with different n-gons (maybe close to n=7)? $\endgroup$ – rozu Oct 5 '18 at 12:05
  • 1
    $\begingroup$ No; as I told, I even did not try to squeeze out the heptagon (and small improvements ARE possible!). But it seems tio me that a similar construction should work for an octagon. Sorry, right now I have no time to make such experiments --- they are time consuming for me (is there anybody to algorithmize them?)... $\endgroup$ – Ilya Bogdanov Oct 5 '18 at 15:33

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.