En matemáticas, la distancia de Fréchet es una medida de similitud entre curvas que tiene en cuenta la ubicación y el orden de los puntos a lo largo de las curvas. Lleva el nombre de Maurice Fréchet .
Definición intuitiva
Imagine a una persona atravesando un camino curvo finito mientras pasea a su perro con una correa, con el perro atravesando un camino curvo finito separado. Cada uno puede variar su velocidad para mantener la correa floja, pero ninguno puede moverse hacia atrás. La distancia de Fréchet entre las dos curvas es la longitud de la correa más corta suficiente para que ambos recorran sus caminos separados de principio a fin. Tenga en cuenta que la definición es simétrica con respecto a las dos curvas; la distancia de Fréchet sería la misma si el perro estuviera paseando a su dueño.
Definicion formal
Dejar ser un espacio métrico . Una curva en es un mapa continuo desde el intervalo unitario hasta, es decir, . Una reparametrización de es un continuo, no decreciente , surjection .
Dejar y ser dos curvas dadas en . Entonces, la distancia de Fréchet entre y se define como el mínimo de todas las reparametrizaciones y de del máximo sobre todo de la distancia en Entre y . En notación matemática, la distancia de Fréchet es
dónde es la función de distancia de.
De manera informal, podemos pensar en el parámetro como el tiempo". Luego, es la posición del perro y es la posición del dueño del perro en el momento (o viceversa). La longitud de la correa entre ellos a la vez es la distancia entre y . Tomando el infimum sobre todas las posibles reparametrizaciones decorresponde a elegir el paseo por los caminos indicados donde se minimiza la longitud máxima de la correa. La restricción que y ser no decreciente significa que ni el perro ni su dueño pueden dar marcha atrás.
La métrica de Fréchet tiene en cuenta el flujo de las dos curvas porque los pares de puntos cuya distancia contribuye a la distancia de Fréchet barren continuamente a lo largo de sus respectivas curvas. Esto hace que la distancia de Fréchet sea una mejor medida de similitud para las curvas que las alternativas, como la distancia de Hausdorff , para conjuntos de puntos arbitrarios. Es posible que dos curvas tengan una distancia de Hausdorff pequeña pero una distancia de Fréchet grande.
La distancia de Fréchet y sus variantes encuentran aplicación en varios problemas, desde la transformación [1] y el reconocimiento de la escritura a mano [2] hasta la alineación de la estructura de la proteína . [3] Alt y Godau [4] fueron los primeros en describir un algoritmo de tiempo polinomial para calcular la distancia de Fréchet entre dos curvas poligonales en el espacio euclidiano , basado en el principio de búsqueda paramétrica . El tiempo de ejecución de su algoritmo espara dos curvas poligonales con m y n segmentos.
El diagrama de espacio libre
Una herramienta importante para calcular la distancia de Fréchet de dos curvas es el diagrama de espacio libre, que fue presentado por Alt y Godau. [4] El diagrama de espacio libre entre dos curvas para un umbral de distancia dado ε es una región bidimensional en el espacio de parámetros que consta de todos los pares de puntos en las dos curvas a una distancia como máximo ε:
La distancia de Fréchet es como máximo ε si y solo si el diagrama de espacio libre contiene una ruta desde la esquina inferior izquierda a la esquina superior derecha, que es monótona tanto en dirección horizontal como vertical.
Como distancia entre distribuciones de probabilidad (la puntuación FID)
Además de medir las distancias entre curvas, la distancia de Fréchet también se puede utilizar para medir la diferencia entre distribuciones de probabilidad . Para dos distribuciones gaussianas multivariadas con medias y y matrices de covarianza y , la distancia de Fréchet entre estas distribuciones es [5]
.
Esta distancia es la base de la distancia de inicio de Fréchet (FID) que se utiliza para comparar las imágenes producidas por una red generativa adversaria con las imágenes reales que se utilizaron para el entrenamiento.
Variantes
La distancia de Fréchet débil es una variante de la distancia de Fréchet clásica sin el requisito de que los puntos finales se muevan monótonamente a lo largo de sus respectivas curvas: el perro y su dueño pueden retroceder para mantener la correa corta entre ellos. Alt y Godau [4] describen un algoritmo más simple para calcular la distancia de Fréchet débil entre curvas poligonales, basado en el cálculo de rutas minimax en un gráfico de cuadrícula asociado .
La distancia de Fréchet discreta , también llamada distancia de acoplamiento , es una aproximación de la métrica de Fréchet para curvas poligonales, definida por Eiter y Mannila. [6] La distancia de Fréchet discreta considera solo las posiciones de la correa donde sus puntos finales están ubicados en los vértices de las dos curvas poligonales y nunca en el interior de un borde. Esta estructura especial permite calcular la distancia de Fréchet discreta en tiempo polinomial mediante un sencillo algoritmo de programación dinámica.
Cuando las dos curvas están incrustadas en un espacio métrico que no es el espacio euclidiano, como un terreno poliédrico o algún espacio euclidiano con obstáculos, la distancia entre dos puntos en las curvas se define más naturalmente como la longitud del camino más corto entre ellos. Se requiere que la correa sea una geodésica que une sus extremos. La métrica resultante entre curvas se llama distancia geodésica de Fréchet . [1] [7] [8] Cook y Wenk [7] describen un algoritmo de tiempo polinomial para calcular la distancia de Fréchet geodésica entre dos curvas poligonales en un polígono simple .
Si además requerimos que la correa debe moverse continuamente en el espacio métrico ambiental, entonces obtenemos la noción de la distancia de Fréchet homotópica [9] entre dos curvas. La correa no puede cambiar de forma discontinua de una posición a otra; en particular, la correa no puede saltar obstáculos y puede barrer una montaña en un terreno solo si es lo suficientemente larga. El movimiento de la correa describe una homotopía entre las dos curvas. Chambers et al. [9] describen un algoritmo de tiempo polinomial para calcular la distancia de Fréchet homotópica entre curvas poligonales en el plano euclidiano con obstáculos.
Ejemplos de
La distancia de Fréchet entre dos círculos concéntricos de radio y respectivamente es Se requiere la correa más larga cuando el dueño se detiene y el perro viaja al lado opuesto del círculo (), y la correa más corta cuando tanto el dueño como el perro caminan a una velocidad angular constante alrededor del círculo ().
Aplicaciones
La distancia de Fréchet se ha utilizado para estudiar la jerarquía visual , un principio de diseño gráfico. [10]
Referencias
- ^ a b Efrat, Alon; Guibas, Leonidas J .; Har-Peled, Sariel ; Mitchell, Joseph SB ; Murali, TM (2002), "Nuevas medidas de similitud entre polilíneas con aplicaciones a la transformación y el barrido de polígonos" (PDF) , Geometría discreta y computacional , 28 (4): 535–569, doi : 10.1007 / s00454-002-2886-1.
- ^ Sriraghavendra, R .; Karthik, K .; Bhattacharyya, Chiranjib (2007), "Enfoque basado en la distancia de Fréchet para la búsqueda de documentos manuscritos en línea", Proc. Novena Conferencia Internacional sobre Análisis y Reconocimiento de Documentos (ICDAR '07) , págs. 461–465, doi : 10.1109 / ICDAR.2007.121.
- ^ Minghui, Jiang; Ying, Xu; Binhai, Zhu (2008), "Alineación estructura-estructura de proteínas con distancia discreta de Fréchet" (PDF) , Journal of Bioinformatics and Computational Biology , 6 (1): 51-64, doi : 10.1142 / S0219720008003278 , PMID 18324745.
- ^ a b c Alt, Helmut; Godau, Michael (1995), "Calcular la distancia de Fréchet entre dos curvas poligonales" (PDF) , International Journal of Computational Geometry and Applications , 5 (1–2): 75–91, doi : 10.1142 / S0218195995000064.
- ^ Dowson, D. C; Landau, B. V (1 de septiembre de 1982). "La distancia de Fréchet entre distribuciones normales multivariadas". Revista de análisis multivariante . 12 (3): 450–455. doi : 10.1016 / 0047-259X (82) 90077-X . ISSN 0047-259X .
- ^ Eiter, Thomas; Mannila, Heikki (1994), Computación de distancia discreta de Fréchet (PDF) , Tech. Informe CD-TR 94/64, Laboratorio Christian Doppler para sistemas expertos, TU Viena, Austria.
- ^ a b Cook, Atlas F., IV; Wenk, Carola (2008), Distancia de Fréchet geodésica con obstáculos poligonales (PDF) , Tech. Informe CS-TR-2008-0010, Universidad de Texas en San Antonio.
- ^ Maheshwari, Anil; Yi, Jiehua (2005), "Sobre el cálculo de la distancia de Fréchet de dos caminos en un poliedro convexo", Proc. 21º Taller europeo sobre geometría computacional (PDF) , págs. 41–44.
- ^ a b Chambers, Erin Wolf; Colin de Verdière, Éric; Erickson, Jeff; Lazard, Sylvain; Lázaro, Francisco; Thite, Shripad (2009), "Distancia de Fréchet homotópica entre curvas, o Pasear a su perro en el bosque en tiempo polinomial" (PDF) , Geometría computacional: Teoría y aplicaciones , 43 (3): 295–311, doi : 10.1016 / j .comgeo.2009.02.008.
- ^ Urano, Yoko; Kurosu, Aaron; Henselman-Petrusek, Gregory; Todorov, Alexander (2021). "La jerarquía visual se relaciona con las impresiones de un buen diseño" . Taller CHI'21 sobre movimientos oculares como interfaz con el estado cognitivo : 1–9. doi : 10.31234 / osf.io / hksf9 .
Otras lecturas
- de Berg, Mark, "Análisis de trayectorias de objetos en movimiento", geometría computacional, dos temas seleccionados (PDF) , págs. 11–75.
- Aronov, Boris ; Har-Peled, Sariel; Knauer, cristiano; Wang, Yusu ; Wenk, Carola (2006), "Distancia de Fréchet para curvas, revisada", Proc. 14th European Symposium on Algorithms (PDF) , Lecture Notes in Computer Science, 4168 , Springer-Verlag, págs. 52–63, arXiv : 1504.07685 , doi : 10.1007 / 11841036_8 , archivado desde el original (PDF) el 12 de junio de 2010.
- Alt, Helmut; Buchin, Maike (2010), "¿Podemos calcular la similitud entre superficies?", Geometría discreta y computacional , 43 : 78–99, arXiv : cs.CG/0703011 , doi : 10.1007 / s00454-009-9152-8.