Rough isometries

An isometry is a map ${f\colon X\rightarrow Y}$ between two metric spaces ${X,Y}$ which preserves all distances: ${d_Y(f(x),f(x')) = d_X(x,x')}$ for all ${x,x'\in X}$ . (After typing a bunch of such formulas, one tends to prefer shorter notation: ${|f(x)f(x')| = |xx'|}$ , with the metric inferred from contexts.) It’s a popular exercise to prove that every isometry from a compact metric space into itself is surjective.

A rough isometry allows additive distortion of distances: ${|\,|f(x)f(x')| - |xx'|\,|\le \epsilon}$ . (As contrasted with bi-Lipschitz maps, which allow multiplicative distortion). Rough isometries ignore small-scale features (in particular, they need not be continuous), but accurately capture the large scale structure of a space. This makes them convenient for studying hyperbolic spaces (trees and their relatives), where the large-scale structure is of interest.

If ${f}$ is an ${\epsilon}$ -rough isometry, then the Gromov-Hausdorff distance ${d_{GH}}$ between ${X}$ and ${f(X)}$ is at most ${\epsilon/2}$ . This follows from a convenient characterization of ${d_{GH}}$ : it is equal to ${\frac12 \inf_R \textrm{dis}\,(R)}$ where the infimum is taken over all subsets ${R\subset X\times Y}$ that project surjectively onto each factor, and ${\textrm{dis}\,(R) = \sup \{|\,|xx'|-|yy'|\,| \colon xRy, \ x'Ry' \} }$ .

Since small-scale features are ignored, it is not quite natural to talk about rough isometries being surjective. A natural concept for them is ${\epsilon}$ -surjectivity, meaning that every point of ${Y}$ is within distance ${\le \epsilon}$ of ${f(X)}$ . When this happens, we can conclude that ${d_{GH}(X,Y)\le 3\epsilon/2}$ , because the Hausdorff distance between ${Y}$ and ${f(X)}$ is at most ${\epsilon}$ .

Recalling that an isometry of a compact metric space ${X}$ into ${X}$ is automatically onto, it is natural to ask whether ${\epsilon}$ -rough isometries of ${X}$ into ${X}$ are ${\epsilon}$ -surjective. This, however, turns out to be false in general.

First example, a finite space: ${X=\{0,1,2,\dots,n\}}$ with the metric ${d(i,j) = i+j}$ (when ${i\ne j}$ ). Consider the backward shift ${f(i)=i-1}$ (and ${f(0)=0}$ ). By construction, this is a rough isometry with ${\epsilon=2}$ . Yet, the point ${n}$ is within distance ${n}$ from ${f(X) = \{0,1,2,\dots, n-1\}}$ .

The above metric can be thought of a the distance one has to travel from ${i}$ to ${j}$ with a mandatory visit to ${0}$ . This makes it similar to the second example.

Second example, a geodesic space: ${X}$ is the graph shown below, a subset of ${\mathbb R^2}$ with the intrinsic (path) metric, i.e., the length of shortest path within the set.

Define ${f(x,y) = ((x-1)^+, (y-1)^+)}$ where ${{\,}^+}$ means the positive part. Again, this is a ${2}$ -rough isometry. The omitted part, shown in red below, contains a ball of radius ${5}$ centered at ${(5,5)}$ . Of course, ${5}$ can be replaced by any positive integer.

Both of these examples are intrinsically high-dimensional: they cannot be accurately embedded into ${\mathbb R^d}$ for low ${d}$ (using the restriction metric rather than the path metric). This raises a question: does there exist ${C=C(d)}$ such that for every compact subset ${K\subset \mathbb R^d}$ , equipped with the restriction metric, every ${\epsilon}$ -rough isometry ${f\colon K\rightarrow K}$ is ${C(d)\epsilon}$ -surjective?

1 thought on “Rough isometries”

Anonymous says:

2015-08-14 at 10:05

The last question is very nice. As you probably already considered, one might guess that it holds for all doubling metric spaces K, with the constant C depending only on the doubling constant. Both your examples get worse and worse doubling constants as they grow. But I don’t see a proof (of either the Euclidean case or the general doubling case) at the moment.

Rough isometries

Related

1 thought on “Rough isometries”

Leave a Reply Cancel reply