Stretch factor

Short description: Mathematical parameter of embeddings

The stretch factor (i.e., bilipschitz constant) 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(f(x),f(y))/d(x,y). The stretch factor of the whole mapping is the supremum 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.

The Johnson–Lindenstrauss lemma asserts that any finite set with n points in a Euclidean space can be embedded into a Euclidean space of dimension O(log n) with distortion 1 + ε, for any constant ε > 0, where the constant factor in the O-notation depends on the choice of ε. This result, and related methods of constructing low-distortion metric embeddings, are important in the theory of approximation algorithms. A major open problem in this area is the GNRS conjecture, which (if true) would characterize the families of graphs that have bounded-stretch embeddings into [math]\displaystyle{ \ell_1 }[/math] spaces as being all minor-closed graph families.

In knot theory, the distortion of a knot is a knot invariant, the minimum stretch factor of any embedding of the knot as a space curve in Euclidean space. Undergraduate researcher John Pardon won the 2012 Morgan Prize for his research showing that there is no upper bound on the distortion of torus knots, solving a problem originally posed by Mikhail Gromov.

In the study of the curve-shortening flow, in which each point of a curve in the Euclidean plane moves perpendicularly to the curve, with speed proportional to the local curvature, (Huisken 1998) proved that the stretch factor of any simple closed smooth curve (with intrinsic distances measured by arc length) changes monotonically. More specifically, at each pair (x,y) that forms a local maximum of the stretch factor, the stretch factor is strictly decreasing, except when the curve is a circle. This property was later used to simplify the proof of the Gage–Hamilton–Grayson theorem, according to which every simple closed smooth curve stays simple and smooth until it collapses to a point, converging in shape to a circle before doing so.