Distancia entre dos subconjuntos de espacio métrico
En matemáticas , la distancia de Hausdorff , o métrica de Hausdorff , también llamada distancia de Pompeya-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 .
Informalmente, 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 alguien puede ser obligado a recorrer 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 de un conjunto al punto más cercano del 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 de .
Definición
Sea un espacio métrico . Para cada par de subconjuntos no vacíos y , la distancia de Hausdorff entre y se define como
donde representa el operador supremo , el operador mínimo y donde cuantifica la distancia de un punto al subconjunto .
Una definición equivalente es la siguiente. [3] Para cada conjunto, sea
cuál es el conjunto de todos los puntos dentro del conjunto (a veces llamado engorde de o una bola generalizada de radio alrededor ). Entonces, la distancia de Hausdorff entre y se define como
De manera equivalente, [1]
donde es la distancia más pequeña desde el punto al conjunto .
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
Entonces . Sin embargo porque , pero .
Pero es cierto que y ; en particular es cierto si están cerrados.
Propiedades
En general, puede ser infinito. Si tanto X como Y están acotados , se garantiza que serán finitos.
si y sólo 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, tal que todo conjunto X′ cuya distancia de Hausdorff a X sea menor que r también interseca a 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.
Si M es completo , entonces también lo es F ( M ). [6]
Si M es compacto, entonces también lo es F ( M ).
La topología de F ( M ) depende sólo de la topología de M , no de la métrica d .
Motivación
La definición de la distancia de Hausdorff se puede derivar 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 Y de M no vacío mediante:
Por ejemplo, d (1, {3,6}) = 2 y d (7, {3,6}) = 1.
Defina una función de "distancia" (no necesariamente simétrica) entre dos conjuntos cualesquiera no vacíos X e Y de M mediante:
Por ejemplo,
Si X e Y son compactos, entonces d ( X , Y ) será finito; d ( X , X )=0; y d hereda la propiedad de desigualdad del triángulo 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étrica, y d ( X , Y ) = 0 no implica que X = Y (sí implica eso ). 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 por computadora , la distancia de Hausdorff se puede utilizar para encontrar una plantilla determinada en una imagen de destino arbitraria. La plantilla y la imagen suelen ser preprocesadas mediante un detector de bordes que genera 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 objetivo 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 en la imagen objetivo con la distancia mínima de Hausdorff a la plantilla puede considerarse el mejor candidato para ubicar la plantilla en el objetivo. En gráficos por computadora, la distancia de Hausdorff se utiliza para medir la diferencia entre dos representaciones diferentes del mismo objeto 3D [8], particularmente cuando se genera nivel de detalle para una visualización eficiente de modelos 3D complejos.
Si es la superficie de la Tierra y es la superficie terrestre de la Tierra, entonces, al encontrar el punto Nemo , vemos que tiene alrededor de 2.704,8 km.
Conceptos relacionados
Una medida de la disimilitud de dos formas viene dada por la distancia de Hausdorff hasta la isometría , denotada DH . Es decir, sean X e Y dos figuras compactas en un espacio métrico M (normalmente un espacio euclidiano ); entonces D H ( X , Y ) es el mínimo de d H ( I ( X ), Y ) entre todas las isometrías I del espacio métrico M consigo mismo. Esta distancia mide qué tan lejos están las formas X e Y de ser isométricas.
La convergencia Gromov-Hausdorff es una idea relacionada: medir la distancia de dos espacios métricos M y N tomando el mínimo de entre todas las incrustaciones isométricas y en algún espacio métrico común L.
^ Bîrsan, Temístocle; Tiba, Dan (2006), "Cien años desde la introducción de la distancia fija por Dimitrie Pompeiu", en Ceragioli, Francesca; Donchev, Asen; Futura, Hitoshi; Martí, Kurt; Pandolfi, Luciano (eds.), Modelado y optimización de sistemas , vol. 199, Boston: Kluwer Academic Publishers , págs. 35–39, doi : 10.1007/0-387-33006-2_4 , ISBN978-0-387-32774-7, señor 2249320
^ Henrikson, Jeff (1999). "Integridad y acotación total de la métrica de Hausdorff" (PDF) . Revista de Matemáticas de Pregrado del MIT : 69–80. Archivado desde el original (PDF) el 23 de junio de 2002.
^ 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 utilizando la herramienta de código abierto MeshLab .