En matemáticas , la distancia de Hausdorff , o métrica de Hausdorff , también llamada distancia de Pompeiu-Hausdorff , [1] [2] mide qué tan lejos están dos subconjuntos de un espacio métrico entre sí. Convierte el conjunto de subconjuntos compactos no vacíos de un espacio métrico en un espacio métrico por derecho propio. Lleva el nombre de Felix Hausdorff y Dimitrie Pompeiu .
De manera informal, dos conjuntos están cerca en la distancia de Hausdorff si cada punto de cualquiera de los conjuntos está cerca de algún punto del otro conjunto. La distancia de Hausdorff es la distancia más larga que puede verse obligado a viajar por un adversario que elige un punto en uno de los dos conjuntos, desde donde luego debe viajar al otro conjunto. En otras palabras, es la mayor de todas las distancias desde un punto en un conjunto al punto más cercano en el otro conjunto.
Esta distancia fue introducida por primera vez por Hausdorff en su libro Grundzüge der Mengenlehre , publicado por primera vez en 1914, aunque un pariente muy cercano apareció en la tesis doctoral de Maurice Fréchet en 1906, en su estudio del espacio de todas las curvas continuas desde.
Definición
Sean X e Y dos subconjuntos no vacíos de un espacio métrico. Definimos su distancia de Hausdorff por
donde sup representa el supremum , inf el infimum , y donde cuantifica la distancia desde un punto al subconjunto .
Equivalentemente,
dónde
es decir, el conjunto de todos los puntos dentro del set (a veces llamado el engorde de o una bola de radio generalizada alrededor ).
Equivalentemente,
es decir, , dónde es la distancia desde el punto al set .
Observación
No es cierto para subconjuntos arbitrarios. que implica
Por ejemplo, considere el espacio métrico de los números reales con la métrica habitual inducida por el valor absoluto,
Llevar
Luego . sin emabargo porque , pero .
Pero es cierto que y ; en particular es cierto si esta cerrado.
Propiedades
- En general, puede ser infinito. Si tanto X como Y están acotados , entonces se garantiza que es finito.
- si y solo si X e Y tienen el mismo cierre.
- Para cada punto x de M y cualquier conjunto no vacío Y , Z de M : d ( x , Y ) ≤ d ( x , Z ) + d H ( Y , Z ), donde d ( x , Y ) es la distancia entre el punto x y el punto más cercano en el conjunto y .
- | diámetro ( Y ) -diámetro ( X ) | ≤ 2 d H ( X , Y ). [4]
- Si la intersección X ∩ Y tiene un interior no vacío, entonces existe una constante r > 0, de manera que cada conjunto X ' cuya distancia Hausdorff de X es menor que r también intersecta Y . [5]
- En el conjunto de todos los subconjuntos de M , d H produce una pseudométrica extendida .
- En el conjunto F ( M ) de todos los subconjuntos compactos no vacíos de M , d H es una métrica.
Motivación
La definición de la distancia de Hausdorff puede derivarse de una serie de extensiones naturales de la función de distancia en el espacio métrico subyacente M , como sigue: [7]
- Defina una función de distancia entre cualquier punto x de M y cualquier conjunto no vacío Y de M mediante:
- Por ejemplo, d (1, {3,6}) = 2 y d (7, {3,6}) = 1.
- Defina una función de distancia entre dos conjuntos no vacíos X e Y de M por:
- Por ejemplo,
- Si X e Y son compactos, entonces d ( X , Y ) será finito; d ( X , X ) = 0; y d hereda la desigualdad triangular propiedad de la función de distancia en M . Tal como está, d ( X , Y ) no es una métrica porque d ( X , Y ) no siempre es simétrico, y d ( X , Y ) = 0 no implica que X = Y (implica que). Por ejemplo, d ({1,3,6,7}, {3,6}) = 2 , pero d ({3,6}, {1,3,6,7}) = 0 . Sin embargo, podemos crear una métrica definiendo la distancia de Hausdorff como:
Aplicaciones
En visión artificial , la distancia de Hausdorff se puede utilizar para encontrar una plantilla determinada en una imagen de destino arbitraria. La plantilla y la imagen a menudo se procesan previamente a través de un detector de bordes que proporciona una imagen binaria . A continuación, cada punto 1 (activado) en la imagen binaria de la plantilla se trata como un punto en un conjunto, la "forma" de la plantilla. De manera similar, un área de la imagen de destino binaria se trata como un conjunto de puntos. Luego, el algoritmo intenta minimizar la distancia de Hausdorff entre la plantilla y alguna área de la imagen de destino. El área de la imagen objetivo con la distancia mínima de Hausdorff a la plantilla puede considerarse la mejor candidata para ubicar la plantilla en el objetivo. [8] En gráficos por computadora, la distancia de Hausdorff se usa para medir la diferencia entre dos representaciones diferentes del mismo objeto 3D [9], particularmente cuando se genera un nivel de detalle para una visualización eficiente de modelos 3D complejos.
Conceptos relacionados
Una medida de la disimilitud de dos formas está dada por Hausdorff distancia de hasta isometría , denota D H . Es decir, sean X e Y dos figuras compactas en un espacio métrico M (generalmente un espacio euclidiano ); entonces D H ( X , Y ) es el mínimo de d H ( I ( X ), Y ) a lo largo de todas las isometrías I del espacio métrico M a sí mismo. Esta distancia mide qué tan lejos están las formas X e Y de ser isométricas.
La convergencia de Gromov-Hausdorff es una idea relacionada: medimos la distancia de dos espacios métricos M y N tomando el mínimo de a lo largo de todas las incrustaciones isométricas y en algún espacio métrico común L .
Ver también
Referencias
- ↑ a b Rockafellar, R. Tyrrell ; Mojados, Roger JB (2005). Análisis variacional . Springer-Verlag. pag. 117. ISBN 3-540-62772-3.
- ^ Bîrsan, Temistocle; Tiba, Dan (2006), "Cien años desde la introducción de la distancia establecida por Dimitrie Pompeiu", en Ceragioli, Francesca; Dontchev, Asen; Futura, Hitoshi; Marti, Kurt; Pandolfi, Luciano (eds.), Modelado y optimización de sistemas , 199 , Boston: Kluwer Academic Publishers , págs. 35–39, doi : 10.1007 / 0-387-33006-2_4 , ISBN 978-0-387-32774-7, MR 2249320
- ^ Munkres, James (1999). Topología (2ª ed.). Prentice Hall . págs. 280–281. ISBN 0-13-181629-2.
- ^ Diámetro y distancia de Hausdorff , Math.SE
- ^ Distancia e intersección de Hausdorff , Math.SE
- ^ Henrikson, Jeff (1999). "Integridad y delimitación total de la métrica de Hausdorff" (PDF) . Revista de pregrado de matemáticas del MIT : 69–80. Archivado desde el original (PDF) el 23 de junio de 2002.
- ^ Barnsley, Michael (1993). Fractales en todas partes . Morgan Kaufmann . págs. Cap. II.6. ISBN 0-12-079069-6.
- ^ Coincidencia basada en Hausdorff
- ^ Cignoni, P .; Rocchini, C .; Scopigno, R. (1998). "Metro: Error de medición en superficies simplificadas". Foro de Gráficos por Computadora . 17 (2): 167-174. CiteSeerX 10.1.1.95.9740 . doi : 10.1111 / 1467-8659.00236 . S2CID 17783159 .
enlaces externos
- Distancia de Hausdorff entre polígonos convexos .
- Uso de MeshLab para medir la diferencia entre dos superficies Un breve tutorial sobre cómo calcular y visualizar la distancia de Hausdorff entre dos superficies 3D trianguladas usando la herramienta de código abierto MeshLab .
- Código MATLAB para distancia de Hausdorff: [1]