El factor de estiramiento de una incrustación mide el factor por el cual la incrustación distorsiona las distancias . Suponga que un espacio métrico S está incrustado en otro espacio métrico T mediante un mapa métrico , una función continua uno a uno f que conserva o reduce la distancia entre cada par de puntos. A continuación, la incrustación da lugar a dos nociones diferentes de la distancia entre los pares de puntos en S . Cualquier par de puntos ( x , y ) en S tiene una distancia intrínseca , la distancia desde xa y en S , y una distancia extrínseca más pequeño, 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 todo el mapeo es el supremo (si existe) de los factores de estiramiento de todos los pares de puntos. El factor de estiramiento también se ha denominado distorsión o dilatación del mapeo.
El factor de estiramiento es importante en la teoría de llaves geométricas , gráficos ponderados que se aproximan a 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 trayectoria más cortas en un gráfico, y la métrica T en la que está incrustado S es el plano euclidiano. Cuando el gráfico y su incrustación son fijos, pero los pesos de los bordes del gráfico pueden variar, el factor de estiramiento se minimiza cuando los pesos son exactamente las distancias euclidianas entre los extremos de los bordes. La investigación en esta área se ha centrado en encontrar gráficos dispersos para un conjunto de puntos dado que tienen un factor de estiramiento bajo. [1]
El lema de Johnson-Lindenstrauss afirma que cualquier espacio métrico finito con n puntos se puede incrustar en un espacio euclidiano de dimensión O (log n ) con distorsión 1 + ε , para cualquier constante ε > 0 , donde el factor constante en la notación O 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 gran problema abierto en esta área es la conjetura de GNRS , que (si es cierta) caracterizaría las familias de gráficos que tienen incrustaciones de estiramiento acotado en espacios como todas las familias de grafos cerrados menores.
En la teoría de nudos , la distorsión de un nudo es invariante , 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 muestra que no existe un límite superior en la distorsión de los nudos del toro , resolviendo un problema originalmente planteado 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 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 usó más tarde para simplificar la demostración del teorema de Gage-Hamilton-Grayson, según el cual cada 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]
Referencias
- ^ Narasimhan, Giri; Smid, Michiel (2007), Geometric Spanner Networks , Cambridge University Press , ISBN 0-521-81513-4.
- ^ Johnson, William B .; Lindenstrauss, Joram (1984), "Extensiones de mapeos de Lipschitz en un espacio de Hilbert", en Beals, Richard; Beck, Anatole; Bellow, Alexandra; et al. (eds.), Conferencia sobre análisis moderno y probabilidad (New Haven, Conn., 1982) , Contemporary Mathematics, 26 , Providence, RI: American Mathematical Society, págs. 189-206 , doi : 10.1090 / conm / 026/737400 , ISBN 0-8218-5030-X, MR 0737400.
- ^ Kehoe, Elaine (abril de 2012), "2012 Morgan Prize", Notices of the American Mathematical Society , 59 (4): 569–571, doi : 10.1090 / noti825.
- ^ Perdón, John (2011), "Sobre la distorsión de nudos en superficies incrustadas", Annals of Mathematics , Second Series, 174 (1): 637–646, arXiv : 1010.1972 , doi : 10.4007 / annals.2011.174.1.21 , MR 2811613.
- ^ Huisken, Gerhard (1998), "Un principio de comparación de distancias para curvas en evolución", The Asian Journal of Mathematics , 2 (1): 127-133, hdl : 11858 / 00-001M-0000-0013-5964-4 , MR 1656553.
- ^ Andrews, Ben; Bryan, Paul (2011), "Curvatura límite para el flujo de acortamiento de la curva mediante la comparación de distancias y una prueba directa del teorema de Grayson", Journal für die Reine und Angewandte Mathematik , 653 : 179-187, arXiv : 0908.2682 , doi : 10.1515 / CRELLE. 2011.026 , MR 2794630.