Gromov-Hausdorff distance between a disk and a circle

Question

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$.

Answer 1

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}$.

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.

Answer 2

Let $P_n=\{V_1,...,V_n\} \subset \partial D^2$ be the set of the vertices of a regular $n-$gon: since the Gromov-Hausdorff distance between $P_n$ and $\partial D^2$ tends to $0$, it is enough to compute $\lim_{n \to \infty} g_n$, where $g_n$ is the Gromov-Hausdorff distance between $P_n$ and $D^2$, so I tried to compute $g_n$ (or at least a lower bound) for some small values of $n$, hoping to see a pattern.

First of all observe that, since any correspondence $R$ has the same distortion as its closure (with respect to the product topology), in the case $R\subseteq P_n \times D^2$ we can assume that the sets $A_i=\{ x \in D^2 | (V_i,x) \in R\}$ are closed; moreover, they must be all nonempty and their union must be the whole $D^2$. If we fix a constant $c \le 2$ and try to find a correspondence $R=\bigcup_{i=i}^n \{V_i\} \times A_i$ of distortion less than $c$, we need any two $A_i$ and $A_j$ to be disjoint if $d(V_i,V_j) \ge c$ and, roughly speaking, not too far from each other if $d(V_i,V_j)$ is small (in particular, $i=j$ gives the condition $diam(A_i)<c$): the main idea is to prove by topological arguments that if $c$ is small enough, it's impossible to satisfy both these conditions at the same time. Here's what I got:

• $n=3$ (just as a warm up): since $D^2$ is connected, we have at least a nonempty intersection, and then $dis(R) \ge \sqrt{3}$; on the other hand, "slicing" $D^2$ into three equal parts achieves the equality. Therefore $g_3=\dfrac{\sqrt{3}}{2}$.

• $n=4$: any $R$ with distortion strictly less than $2$ must satisfy $A_1 \cap A_3=A_2 \cap A_4=\varnothing$. We can then define $f:D^2 \to \Delta$, where $\Delta \subset \mathbb{R}^4$ is the $3-$simplex spanned by $\{e_1,e_2,e_3,e_4\}$ and the $i-$th coordinate of $f(x)$ is $\dfrac{d(x,A_i)}{\sum\limits_{j=1}^4 d(x,A_j)}$: since at least one of the four distances is zero, $f$ actually takes values in $\partial \Delta$, but it avoids two opposite edges (in general, if $A_{i_1} \cap ... \cap A_{i_r}=\varnothing$, it avoids the cell $\{x_{i_1}=...=x_{i_r}=0\}$ of $\partial \Delta$), so it takes values in their complement $C\cong \mathbb{R}\times S^1$, which is easily seen to admit a projection $\pi:C \to S^1$ such that each fiber is contained in a single face of $\partial \Delta$. We can now take the lift $\phi$ of $\pi \circ f$ to the universal cover of $S^1$, and applying the Borsuk-Ulam theorem to $\phi|_{\partial D^2}$ we conclude that there are two antipodal points of $\partial D^2$ lying in the same $A_i$, but this contradicts $dis(R)<2$. Therefore $g_4=1$ ($1$ is also an upper bound since it is half the diameter of both spaces).

Now I claim that this argument can be generalized as follows: given $1 \le k<\dfrac{n}{2}$, if every nonempty intersection $A_{i_1} \cap ... \cap A_{i_r}$ satisfies $\{i_1,...,i_r\} \subseteq \{s,s+1,...,s+k\}$ for some $s$ (where the indices must be thought modulo $n$), then there exists an index $t$ such that $A_t \cup ... \cup A_{t+k-1}$ contains two antipodal points of $\partial D^2$, and then $dis(R) \ge 2-2\sin\left( \dfrac{(k-1)\pi}{n}\right)$. The idea is still to construct a continuous $\pi$ from the complement of a subcomplex of $\partial \Delta$ to $S^1$, such that each fiber is contained in a union of $k$ "consecutive" faces: it should be possible, but I ended up doing complicated calculations and I left them incomplete.

If what I wrote until here is correct, using $k=1$ we can prove by contradiction that $g_n \ge \sin\left( \dfrac{2 \pi}{n}\right)$ $\forall n \ge 4$, which appears to be optimal up to $n=8$ (I found the optimizing correspondences), but then we have a new issue: for any $R$ with distortion less than $2\sin \left(\dfrac{3 \pi}{n}\right)$, we can use $k=2$ and get $dis(R) \ge 2-2\sin\left( \dfrac{\pi}{n} \right)$, so that $g_n \ge \min \left( \sin\left( \dfrac{3\pi}{n} \right), 1-\sin\left( \dfrac{\pi}{n} \right) \right)$: this is a stronger bound if $n \ge 9$, and it equals $1-\sin\left( \dfrac{\pi}{n} \right)$ if $9 \le n <12$.

More generally, if we define $k_n$ as the smallest integer such that $1-\sin\left( \dfrac{k_n \pi}{n} \right) < \sin \left( \dfrac{(k_n+2) \pi}{n} \right)$, we have $g_n \ge 1-\sin\left( \dfrac{k_n \pi}{n} \right)$. I believe that this is optimal, since it seems possible to generalize the construction of the optimizing correspondences I had found for $n \le 8$: if this is true, one can prove that $k_n$ is asymptotically $\dfrac{n}{6}$, and then $\lim_{n \to \infty} g_n=\dfrac{1}{2}$.

EDIT: that was incomplete. For every $1 \le k < \dfrac{n}{3}$, we have $g_n \ge \min \left(1-\sin \left( \dfrac{(k-1) \pi}{n} \right),\sin \left( \dfrac{(k+1) \pi}{n} \right) \right)$, so that $g_n$ is bounded by the maximum of all these values. Keeping the previous definition of $k_n$, which turns out to be $\left\lfloor \dfrac{n}{6} \right\rfloor$ for $n \ge 9$, we have

$g_n \ge \max \left( \sin\left(\dfrac{(k_n+1)\pi}{n}\right),1-\sin\left(\dfrac{k_n\pi}{n}\right) \right)=\begin{cases} \sin\left(\dfrac{(k_n+1)\pi}{n}\right) & \text{if} \quad 6k_n \le n < 6k_n+3\\ 1-\sin\left(\dfrac{k_n\pi}{n}\right) & \text{if} \quad 6k_n+3 \le n <6k_n+6 \end{cases}$.

I'm starting to doubt that this is optimal, but assuming that it is, the limit for $n \to \infty$ is still $\dfrac{1}{2}$.