Factor de estiramiento

El factor de estiramiento (es decir, la constante de bilipschitz ) de una incrustación mide el factor por el cual la incrustación distorsiona las distancias . Supóngase que un espacio métrico S está incrustado en otro espacio métrico T mediante una función métrica , una función biunívoca continua f que preserva o reduce la distancia entre cada par de puntos. Entonces la incrustación da lugar a dos nociones diferentes de distancia entre pares de puntos en S. Cualquier par de puntos ( x , y ) en S tiene una distancia intrínseca , la distancia de x a y en S , y una distancia extrínseca más pequeña, la distancia de f ( x ) a f ( y ) en T. El factor de estiramiento del par es la relación entre estas dos distancias, d ( f ( x ), f ( y ))/ d ( x , y ) . El factor de estiramiento de toda la aplicación es el supremo de los factores de estiramiento de todos los pares de puntos. El factor de estiramiento también se ha llamado distorsión ^{[ discutido – discutido ]} o dilatación del mapeo.

El factor de estiramiento es importante en la teoría de los spanners geométricos , grafos ponderados que aproximan las distancias euclidianas entre un conjunto de puntos en el plano euclidiano . En este caso, la métrica incrustada S es un espacio métrico finito, cuyas distancias son las longitudes de ruta más cortas en un grafo, y la métrica T en la que S está incrustado es el plano euclidiano. Cuando el grafo y su incrustación son fijos, pero los pesos de los bordes del grafo pueden variar, el factor de estiramiento se minimiza cuando los pesos son exactamente las distancias euclidianas entre los puntos finales de los bordes. La investigación en esta área se ha centrado en encontrar grafos dispersos para un conjunto de puntos dado que tengan un factor de estiramiento bajo. ^[1]

El lema de Johnson-Lindenstrauss afirma que cualquier conjunto finito con n puntos en un espacio euclidiano puede ser incrustado en un espacio euclidiano de dimensión O (log  n ) con distorsión 1 + ε , para cualquier constante ε > 0 , donde el factor constante en la O -notación depende de la elección de  ε . ^[2] Este resultado, y los métodos relacionados para construir incrustaciones métricas de baja distorsión, son importantes en la teoría de algoritmos de aproximación . Un importante problema abierto en esta área es la conjetura GNRS , que (de ser cierta) caracterizaría a las familias de grafos que tienen incrustaciones de estiramiento acotado en espacios como todas familias de grafos menores-cerrados.${\displaystyle \ell _{1}}$

En la teoría de nudos , la distorsión de un nudo es un invariante del nudo , el factor de estiramiento mínimo de cualquier incrustación del nudo como una curva espacial en el espacio euclidiano . El investigador universitario John Pardon ganó el Premio Morgan 2012 por su investigación que demuestra que no existe un límite superior para la distorsión de los nudos toroidales , resolviendo un problema planteado originalmente por Mikhail Gromov . ^{[3] [4]}

En el estudio del flujo de acortamiento de curvas , en el que cada punto de una curva en el plano euclidiano se mueve perpendicularmente a la curva, con una velocidad proporcional a la curvatura local, Huisken (1998) demostró que el factor de estiramiento de cualquier curva suave cerrada simple (con distancias intrínsecas medidas por la longitud del arco) cambia monótonamente. Más específicamente, en cada par ( x , y ) que forma un máximo local del factor de estiramiento, el factor de estiramiento es estrictamente decreciente, excepto cuando la curva es un círculo. Esta propiedad se utilizó más tarde para simplificar la prueba del teorema de Gage-Hamilton-Grayson, según el cual toda curva suave cerrada simple permanece simple y suave hasta que colapsa en un punto, convergiendo en forma a un círculo antes de hacerlo. ^{[5] [6]}