View source for Stretch factor

{{Use American English|date = February 2019}}
{{Short description|Mathematical parameter of embeddings}}
{{Use mdy dates|date = February 2019}}
{{distinguish|text=the stretch factor of a [[pseudo-Anosov map]]}}
The '''stretch factor''' (i.e., '''[[Lipschitz continuity#Definition|bilipschitz constant]]''') of an [[embedding]] measures the factor by which the embedding distorts [[distance]]s. Suppose that one [[metric space]] {{mvar|S}} is embedded into another metric space {{mvar|T}} by a [[metric map]], a continuous one-to-one function {{mvar|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 {{mvar|S}}. Any pair of points {{math|(''x'',''y'')}} in {{mvar|S}} has both an [[intrinsic metric|intrinsic distance]], the distance from {{mvar|x}} to {{mvar|y}} in {{mvar|S}}, and a smaller extrinsic distance, the distance from {{math|''f''(''x'')}} to {{math|''f''(''y'')}} in {{mvar|T}}. The stretch factor of the pair is the ratio between these two distances, {{math|''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'''{{Disputed inline|Terminology: distortion|date=June 2022}} or '''dilation''' of the mapping.

The stretch factor is important in the theory of [[geometric spanner]]s, [[weighted graph]]s that approximate the [[Euclidean distance]]s between a set of points in the [[Euclidean plane]]. In this case, the embedded metric {{mvar|S}} is a finite metric space, whose distances are [[Shortest path problem|shortest path lengths]] in a graph, and the metric {{mvar|T}} into which {{mvar|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 graph]]s for a given point set that have low stretch factor.<ref>{{citation|first1=Giri|last1=Narasimhan|first2=Michiel|last2=Smid|title=Geometric Spanner Networks|publisher=[[Cambridge University Press]]|year=2007|isbn=0-521-81513-4}}.</ref>

The [[Johnson–Lindenstrauss lemma]] asserts that any finite set with {{mvar|n}} points in a Euclidean space can be embedded into a Euclidean space of dimension {{math|''O''(log&nbsp;''n'')}} with distortion {{math|1 + ''&epsilon;''}}, for any constant {{math|''&epsilon;'' > 0}}, where the constant factor in the {{mvar|O}}-notation depends on the choice of&nbsp;{{mvar|&epsilon;}}.<ref>{{citation
 | last1 = Johnson
 | first1 = William B.
 | author1-link = William B. Johnson (mathematician)
 | last2 = Lindenstrauss
 | first2 = Joram
 | author2-link = Joram Lindenstrauss
 | contribution = Extensions of Lipschitz mappings into a Hilbert space
 | doi = 10.1090/conm/026/737400
 | location = Providence, RI
 | mr = 737400
 | pages = [https://archive.org/details/conferenceinmode0000conf/page/189 189–206]
 | publisher = American Mathematical Society
 | series = Contemporary Mathematics
 | title = Conference in modern analysis and probability (New Haven, Conn., 1982)
 | volume = 26
 | year = 1984
 | editor1-last = Beals
 | editor1-first = Richard
 | editor2-last = Beck
 | editor2-first = Anatole
 | editor3-last = Bellow
 | editor3-first = Alexandra
 | display-editors = 3
 | editor4-last = Hajian
 | editor4-first = Arshag
 | isbn = 0-8218-5030-X
 | url-access = registration
 | url = https://archive.org/details/conferenceinmode0000conf/page/189
 }}.</ref> This result, and related methods of constructing low-distortion metric embeddings, are important in the theory of [[approximation algorithm]]s. 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>\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 knot]]s, solving a problem originally posed by [[Mikhail Leonidovich Gromov|Mikhail Gromov]].<ref>{{citation|title=2012 Morgan Prize|journal=[[Notices of the American Mathematical Society]]|date=April 2012|doi=10.1090/noti825|pages=569–571|volume=59|issue=4|first=Elaine|last=Kehoe|doi-access=free}}.</ref><ref>{{citation
 | last = Pardon | first = John
 | doi = 10.4007/annals.2011.174.1.21
 | issue = 1
 | journal = [[Annals of Mathematics]]
 | mr = 2811613
 | pages = 637–646
 | series = Second Series
 | title = On the distortion of knots on embedded surfaces
 | arxiv = 1010.1972| volume = 174
 | year = 2011}}.</ref>

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, {{harvtxt|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 {{math|(''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.<ref>{{citation
 | last = Huisken | first = Gerhard | authorlink = Gerhard Huisken
 | issue = 1
 | journal = The Asian Journal of Mathematics
 | mr = 1656553
 | pages = 127–133
 | title = A distance comparison principle for evolving curves
 | volume = 2
 | year = 1998| hdl = 11858/00-001M-0000-0013-5964-4
 | hdl-access = free
 }}.</ref><ref>{{citation
 | last1 = Andrews | first1 = Ben
 | last2 = Bryan | first2 = Paul
 | arxiv = 0908.2682
 | doi = 10.1515/CRELLE.2011.026
 | journal = [[Crelle's Journal|Journal für die Reine und Angewandte Mathematik]]
 | mr = 2794630
 | pages = 179–187
 | title = Curvature bound for curve shortening flow via distance comparison and a direct proof of Grayson's theorem
 | volume = 653
 | year = 2011}}.</ref>

==References==
{{reflist}}

[[Category:Metric geometry]]