Stretch factor

In mathematics, the stretch factor of an embedding measures the factor by which the embedding distorts distances. Suppose that one metric space S is embedded into another metric space T by a metric map, a continuous one-to-one function f that preserves or reduces the distance between every pair of points. Then the embedding gives rise to two different notions of distance between pairs of points in S. Any pair of points (x,y) in S has both an intrinsic distance, the distance from x to y in S, and a smaller extrinsic distance, the distance from f(x) to f(y) in T. The stretch factor of the pair is the ratio between these two distances, d(x,y)/d(f(x),f(y)). The stretch factor of the whole mapping is the supremum (if it exists) of the stretch factors of all pairs of points. The stretch factor has also been called the distortion or dilation of the mapping.

The stretch factor is important in the theory of geometric spanners, weighted graphs that approximate the Euclidean distances between a set of points in the Euclidean plane. In this case, the embedded metric S is a finite metric space, whose distances are shortest path lengths in a graph, and the metric T into which S is embedded is the Euclidean plane. When the graph and its embedding are fixed, but the graph edge weights can vary, the stretch factor is minimized when the weights are exactly the Euclidean distances between the edge endpoints. Research in this area has focused on finding sparse graphs for a given point set that have low stretch factor.

...
Wikipedia