Return to Answer

First of all observe that, since any correspondence $R$ has the same distortion as its closure (with respect to the product topology), we can assume that the sets $A_i=R \cap (\{V_i\}\times D^2)$ 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 distinct $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: 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:

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

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

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:

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.

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

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), we can assume that the sets $A_i=R \cap (\{V_i\}\times D^2)$ 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 distinct $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: 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 the 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 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}$.

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), we can assume that the sets $A_i=R \cap (\{V_i\}\times D^2)$ 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 distinct $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: 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 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}$.