Distancia Frechet

La distancia de Fréchet es una medida de la similitud de las curvas , teniendo en cuenta el número y el orden de los puntos a lo largo de las curvas. La distancia lleva el nombre del matemático francés Maurice Fréchet .

Definición intuitiva

Imagine un perro caminando por una curva, sujeto con una correa por el dueño del perro mientras camina por otra curva. Ambos pasan del punto de partida al punto final, cambiando de velocidad, pero sin regresar. La distancia de Fréchet entre estas dos curvas es la longitud de la correa más corta que se puede conducir a través de las curvas. No la correa más corta con la que puedas recorrer todos los caminos, sino la más corta con la que puedas recorrer el camino.

La definición es simétrica en dos curvas: puedes pensar que el perro está paseando al dueño.

Formal definición

Sea un espacio métrico . Una curva en el espacio es un mapeo continuo de un segmento unitario en , es decir . La reparametrización de un segmento es una sobreyección continua no decreciente . $S$ $A$ $S$ $S$ ${\ estilo de visualización A: [0,1] \ flecha derecha S}$ $\alfa$ $[0,1]$ ${\ estilo de visualización \ alfa: [0,1] \ flecha derecha [0,1]}$

Sean y sean dos curvas en . Entonces la distancia de Fréchet entre y se define como el límite inferior exacto sobre todas las reparametrizaciones y el intervalo sobre todos los máximos de las distancias entre y . En notación matemática, la distancia de Fréchet es $A$ $B$ $S$ $A$ $B$ $\alfa$ $\beta$ $[0,1]$ ${\ estilo de visualización t \ en [0,1]}$ $S$ ${\ estilo de visualización A (\ alfa (t))}$ ${\ estilo de visualización B (\ beta (t))}$ ${\ estilo de visualización F (A, B)}$

$F(A,B)=\inf _{\alpha ,\beta }\,\,\max _{t\in [0,1]}\,\,{\Bigg \{}d{\ Grande (}A(\alpha (t)),\,B(\beta (t)){\Grande)}{\Bigg \))$ ,

donde es la función distancia espacial . $d$ $S$

Informalmente, podemos pensar en el parámetro como "tiempo". Entonces es la posición del perro, y es la posición del dueño del perro en el tiempo (o viceversa). La longitud de la correa entre ellos en el momento del tiempo es igual a la distancia entre y . Tomar el ínfimo sobre todas las reparametrizaciones posibles del segmento corresponde a elegir un paso por las curvas, en el que se minimiza la longitud máxima del líder. La restricción de que y no disminuya significa que ni el perro ni su dueño pueden dar marcha atrás. $t$ ${\ estilo de visualización A (\ alfa (t))}$ ${\ estilo de visualización B (\ beta (t))}$ $t$ $t$ ${\ estilo de visualización A (\ alfa (t))}$ ${\ estilo de visualización B (\ beta (t))}$ $[0,1]$ $\alfa$ $\beta$

La métrica de Fréchet tiene en cuenta el flujo de dos curvas, ya que pares de puntos, cuya distancia determina la distancia de Fréchet, "corren" a lo largo de las curvas. Esto hace que la distancia de Fréchet sea una mejor medida de similitud de curvas que la métrica de Hausdorff para un conjunto arbitrario de puntos. Dos curvas pueden tener una pequeña distancia de Hausdorff pero una gran distancia de Fréchet.

La distancia de Fréchet y sus variaciones encuentran aplicaciones en varios problemas, desde morphing [1] y reconocimiento de escritura a mano [2] hasta la ubicación de estructuras de proteínas [3] . Alt y Godau [4] fueron los primeros en describir un algoritmo de tiempo polinomial para calcular la distancia de Fréchet entre dos líneas quebradas en el espacio euclidiano , basado en los principios de búsqueda paramétrica . El tiempo de ejecución de su algoritmo es igual para dos líneas discontinuas con m y n segmentos. $O(mn\cdot \log(mn))$

Diagrama de espacio libre

Un medio importante para calcular la distancia de Fréchet entre dos curvas es el diagrama de espacio libre propuesto por Alt y Godau [4] . El diagrama del espacio libre entre dos curvas para un umbral de distancia dado ε es una región bidimensional en el espacio de parámetros, que consiste en todos los pares de puntos de dos curvas que están a una distancia que no excede ε:

$D_{\varepsilon }(A,B):=\{\,(\alpha ,\beta )\in [0,1]^{2}\mid d(A(\alpha ),B(\ beta ))\leq\varepsilon\,\}$

La distancia de Fréchet no excede ε si y solo si el diagrama de espacio libre contiene un camino desde la esquina inferior izquierda hasta la esquina superior derecha que es monótono tanto horizontal como verticalmente. ${\ estilo de visualización F (A, B)}$ $D_{\varepsilon}(A,B)$

Opciones

La distancia Fréchet débil es una variante de la distancia Fréchet clásica sin el requisito de monotonía de movimiento a lo largo de las curvas, el perro y su dueño pueden invertir el movimiento. Alt y Godau [4] describieron un algoritmo simple para calcular la distancia de Fréchet débil entre líneas quebradas, basado en el cálculo del camino minimax en la red acoplada .

La distancia discreta de Fréchet , también llamada distancia entrelazada , es una aproximación de la métrica de Fréchet para líneas quebradas definida por Ayter y Mannila [5] . La distancia discreta de Fréchet considera solo las posiciones del líder en los vértices de dos líneas quebradas y nunca dentro de un borde. Esta estructura especial permite calcular la distancia discreta de Fréchet en tiempo polinomial utilizando un algoritmo de programación dinámica simple.

Si dos curvas están incrustadas en un espacio métrico no euclidiano, como un relieve poliédrico , o están incrustadas en un espacio euclidiano obstruido, es natural definir la distancia entre dos puntos en las curvas como la longitud del menor camino entre ellos. La correa en este caso es una geodésica que conecta dos puntos. La métrica resultante entre las curvas se denomina distancia geodésica de Fréchet [1] [6] [7] . Cook y Wenk [6] describieron un algoritmo de tiempo polinomial para calcular la distancia geodésica de Fréchet entre dos líneas discontinuas en un polígono simple .

Si requerimos que la correa se mueva continuamente en el espacio métrico circundante, obtenemos la noción de distancia homotópica de Fréchet [8] entre dos curvas. La correa no puede "saltar" de una posición a otra y, en particular, no puede "saltar" obstáculos y solo puede "saltar" montañas si es lo suficientemente largo. El movimiento de la correa describe una homotopía entre dos curvas. Chambers y otros [8] describieron un algoritmo de tiempo polinomial para calcular la distancia homotópica de Fréchet entre líneas discontinuas en un plano euclidiano obstruido.

Ejemplos

La distancia de Fréchet entre dos círculos concéntricos de radios y es igual a . La correa más grande se necesita cuando el dueño está de pie y el perro corre hacia el punto opuesto del círculo ( ), y la correa más pequeña se necesita cuando el dueño y el perro se mueven a la misma velocidad angular alrededor del círculo ( ). $r_{1}$ $r_{2}$ ${\ estilo de visualización |r_{1}-r_{2}|}$ ${\displaystyle r_{1}+r_{2))$ ${\ estilo de visualización |r_{1}-r_{2}|}$

Notas

↑ 1 2 Efrat, Guibas, Har-Peled, Mitchell, Murali, 2002 , p. 535–569.
↑ Sriraghavendra, Karthik, Bhattacharyya, 2007 , pág. 461–465.
↑ Minghui, Ying, Binhai, 2008 , pág. 51–64.
↑ 1 2 3 Alt, Godau, 1995 , p. 75–91.
↑ Eiter, Mannila, 1994 .
↑ 12 Cook, Wenk, 2008 .
↑ Maheshwari, Yi, 2005 , pág. 41–44.
↑ 1 2 Chambers et al., 2009 , p. 295–311.

Literatura

Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph SB Mitchell, TM Murali. Nuevas medidas de similitud entre polilíneas con aplicaciones para morphing y barrido de polígonos // Geometría discreta y computacional . - 2002. - T. 28 , núm. 4 . - S. 535-569 . -doi : 10.1007/ s00454-002-2886-1 .
R. Sriraghavendra, K. Karthik, Chiranjib Bhattacharyya. proc. 9ª Conferencia Internacional sobre Análisis y Reconocimiento de Documentos (ICDAR '07). - 2007. - S. 461-465. -doi : 10.1109/ ICDAR.2007.121 .
Jiang Minghui, Xu Ying, Zhu Binhai. Alineación estructura-estructura de proteínas con distancia discreta de Fréchet // Journal of Bioinformatics and Computational Biology. - 2008. - T. 6 , núm. 1 . - S. 51-64 . -doi : 10.1142/ S0219720008003278 . — PMID 18324745 .
Helmut Alt, Michael Godau. Cálculo de la distancia de Fréchet entre dos curvas poligonales // Revista internacional de geometría computacional y aplicaciones. - 1995. - V. 5 , núm. 1-2 . - S. 75-91 . - doi : 10.1142/S0218195995000064 .
Thomas Eiter, Heikki Mannila. Cálculo de la distancia discreta de Frechet. - Laboratorio Christian Doppler para Sistemas Expertos, TU Viena, Austria, 1994. - (Informe técnico CD-TR 94/64).
Atlas F. Cook, Carola Wenk. Distancia geodésica Frechet con obstáculos poligonales. - Universidad de Texas en San Antonio, 2008. - (Informe técnico CS-TR-2008-0010).
Anil Maheshwari, Jiehua Yi. proc. 21º Taller Europeo de Geometría Computacional. - 2005. - S. 41-44.
Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite. Distancia homotópica de Fréchet entre curvas, o Paseando a tu perro por el bosque en tiempo polinomial // Geometría computacional: teoría y aplicaciones . - 2009. - T. 43 . - S. 295-311 . -doi : 10.1016/ j.comgeo.2009.02.008 . (enlace no disponible)

Lectura para leer más

Marcos de Berg. Geometría computacional, dos temas seleccionados. - S. 11-75. .
Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk. proc. 14º Simposio Europeo de Algoritmos . - Springer-Verlag, 2006. - T. 4168. - S. 52-63. — (Apuntes de clase en informática). -doi : 10.1007/ 11841036_8 . .
Helmut Alt, Maike Buchin. ¿Podemos calcular la similitud entre superficies? // Geometría Discreta y Computacional . - 2010. - T. 43 . - S. 78-99 . -doi : 10.1007/ s00454-009-9152-8 . — arXiv : cs.CG/0703011 . .