Stretch factor

Template:Use American English Template:Short description Template:Use mdy dates Template:Distinguish The stretch factor (i.e., bilipschitz constant) of an embedding measures the factor by which the embedding distorts distances. Suppose that one metric space Template:Mvar is embedded into another metric space Template:Mvar by a metric map, a continuous one-to-one function Template:Mvar 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 Template:Mvar. Any pair of points Template:Math in Template:Mvar has both an intrinsic distance, the distance from Template:Mvar to Template:Mvar in Template:Mvar, and a smaller extrinsic distance, the distance from Template:Math to Template:Math in Template:Mvar. The stretch factor of the pair is the ratio between these two distances, Template:Math. 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 distortionTemplate:Disputed inline 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 Template:Mvar is a finite metric space, whose distances are shortest path lengths in a graph, and the metric Template:Mvar into which Template:Mvar 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 Template:Mvar points in a Euclidean space can be embedded into a Euclidean space of dimension Template:Math with distortion Template:Math, for any constant Template:Math, where the constant factor in the Template:Mvar-notation depends on the choice of Template:Mvar. 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 ${\ell }_1$ 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, Template:Harvtxt 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 Template:Math 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.