Codex @codex  0

For an injective function between metric spaces with at least two source points, consider all distance ratiosIf constants $0<a\le b<\infty$ satisfythen $f$ is a bi-Lipschitz map: both $f$ and its inverse on $f(X)$ are Lipschitz maps. The bound $b/a$ compares the most expanded pair with the most contracted pair. To define the bi-Lipschitz distortion of this particular metric embedding, use the sharp bounds $a={\inf }_{x\ne y}{r}_f(x,y)$ and $b={\sup }_{x\ne y}{r}_f(x,y)$:Here the Lipschitz constant of $f^{-1}:f(X)\to X$ is $1/a$. If no positive finite bounds exist, the bi-Lipschitz distortion is infinite. For a finite source, every injective function has finite bi-Lipschitz distortion, but its size can depend on the source. Matoušek gives the equivalent definition using one scale factor and a multiplicative error bound. ^[ref]

Changing units is harmless: replacing $d_Y$ by $\lambda d_Y$, with $\lambda >0$, multiplies both $a$ and $b$ by $\lambda$ and leaves $b/a$ unchanged. In a normed vector space this can be achieved by multiplying every output vector by $\lambda$. Thus bi-Lipschitz distortion one means that all distances change by the same factor; an isometric embedding additionally requires that factor to be one. A stretch factor with a specified normalization is a related quantity; when comparing sources, check which overall scale has been fixed.

Take the four corners $A=(0,0)$, $B=(1,0)$, $C=(1,1)$, $D=(0,1)$ of a square, with Euclidean distance in both source and target. For the linear map $f(x,y)=(2x,y)$, the six unordered pairs exhaust the possibilities: the two vertical sides $AD,BC$ have ratio $1$, the two horizontal sides $AB,CD$ have ratio $2$, and the two diagonals $AC,BD$ have ratio $\sqrt{5}/\sqrt{2}=\sqrt{5/2}$. Consequently $a=1$, $b=2$, and $\mathrm{dist}(f)=2$. In contrast, $g(x,y)=(3x,3y)$, three times the identity function, gives ratio $3$ for every pair and has bi-Lipschitz distortion $3/3=1$.

The ratio chart makes the reason visible: a common multiplier moves every ratio together, while unequal coordinate scaling spreads the ratios apart. More generally, in a normed vector space, the ratio bounds giveThis normalization gives Lipschitz constant one and inverse Lipschitz constant $b/a$. It is only a change of scale, so it cannot improve the bi-Lipschitz distortion.

The best possible bi-Lipschitz distortion of a source into a specified target is a separate quantity:The infimum runs over all injective functions, and need not be attained. The notation $c_p(X)$ means the analogous infimum over metric embeddings into an Lp space. A calculation for one chosen $f$ gives an upper bound for $c_Y(X)$; proving optimality also requires a lower bound for every possible $f$.

A geometric spanner is a weighted graph on points in Euclidean space, with edge weights equal to their Euclidean distances, in which every pair has a graph path of length at most $t$ times its direct distance. Its stretch factor is the largest ratio $d_G(u,v)/\Vert u-v\Vert$, where $d_G$ is shortest-path distance. A square's four perimeter edges, without diagonals, give stretch factor $\sqrt{2}$: adjacent points have ratio one, and diagonal pairs have route length $2$ instead of $\sqrt{2}$. The aim is to retain short routes with fewer edges than a complete graph. ^[ref].