= Stretch factor
{title2=$t(f)=\sup_{x\ne y}d_X(x,y)/d_Y(f(x),f(y))$}
{wiki}
For an <injective function> that does not increase distances, one stretch-factor convention measures the largest compression that must be undone:
$$
t(f)=\sup_{x\ne y}\frac{d_X(x,y)}{d_Y(f(x),f(y))}
=\operatorname{Lip}(f^{-1}).
$$
If the sharp <Lipschitz constant> of $f$ is one, this equals <bi-Lipschitz distortion>. Fixing the scale matters: uniform compression $f(x)=x/2$ has stretch factor two in this convention, but <bi-Lipschitz distortion> one. In a <geometric spanner>, the corresponding stretch factor is the largest graph-route distance divided by direct <Euclidean distance>; the graph-to-Euclidean identification does not increase distances. https://people.scs.carleton.ca/~michiel/encyc_geometric_spanners.pdf[Gudmundsson, Narasimhan and Smid, Geometric Spanners, §1: the stretch-factor convention]{ref}.
Back to article page
