Distancia de Hausdorff

Distancia entre dos subconjuntos del espacio métrico

En matemáticas , la distancia de Hausdorff , o métrica de Hausdorff , también llamada distancia de Pompeiu–Hausdorff , ^{[1] [2]} mide la distancia entre dos subconjuntos de un espacio métrico . Convierte el conjunto de subconjuntos compactos no vacíos de un espacio métrico en un espacio métrico por derecho propio. Recibe su nombre en honor a Felix Hausdorff y Dimitrie Pompeiu .

De manera informal, dos conjuntos están próximos en la distancia de Hausdorff si cada punto de cualquiera de ellos está próximo a algún punto del otro conjunto. La distancia de Hausdorff es la distancia más larga que un adversario puede obligar a alguien a recorrer si 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 hasta el 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 a partir de . ${\displaystyle [0,1]\to \mathbb {R} ^{3}}$

Definición

Componentes del cálculo de la distancia de Hausdorff entre la curva verde X y la curva azul Y.

Sea un espacio métrico . Para cada par de subconjuntos no vacíos y , la distancia de Hausdorff entre y se define como ${\displaystyle (M,d)}$ ${\displaystyle X\subset M}$ ${\displaystyle Y\subset M}$ ${\displaystyle X}$ ${\displaystyle Y}$

$${\displaystyle d_{\mathrm {H} }(X,Y):=\max \left\{\,\sup _{x\in X}d(x,Y),\ \sup _{y\in Y}d(X,y)\,\right\},}$$

donde representa el operador supremo , el operador ínfimo y donde cuantifica la distancia de un punto al subconjunto . ${\displaystyle \operatorname {sup} }$ ${\displaystyle \operatorname {inf} }$ ${\displaystyle d(a,B):=\inf _{b\in B}d(a,b)}$ ${\displaystyle a\in X}$ ${\displaystyle B\subseteq X}$

Una definición equivalente es la siguiente. ^[3] Para cada conjunto sea que es el conjunto de todos los puntos dentro del conjunto (a veces llamado el -engorde de o una bola generalizada de radio alrededor de ). Entonces, la distancia de Hausdorff entre y se define como ${\displaystyle X\subset M,}$ $${\displaystyle X_{\varepsilon }:=\bigcup _{x\in X}\{z\in M\mid d(z,x)\leq \varepsilon \},}$$ ${\displaystyle \varepsilon }$ ${\displaystyle X}$ ${\displaystyle \varepsilon }$ ${\displaystyle X}$ ${\displaystyle \varepsilon }$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle Y}$ $${\displaystyle d_{H}(X,Y):=\inf\{\varepsilon \geq 0\mid X\subseteq Y_{\varepsilon }{\text{ and }}Y\subseteq X_{\varepsilon }\}.}$$

Equivalentemente, ^[1] donde es la distancia más pequeña desde el punto hasta el conjunto . $${\displaystyle {\begin{aligned}d_{H}(X,Y)&=\sup _{w\in M}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|\\&=\sup _{w\in X\cup Y}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|\\&=\sup _{w\in M}|d(w,X)-d(w,Y)|,\end{aligned}}}$$ ${\displaystyle d(w,X):=\inf _{x\in X}d(w,x)}$ ${\displaystyle w}$ ${\displaystyle X}$

Observación

No es cierto para subconjuntos arbitrarios que implican ${\displaystyle X,Y\subset M}$ ${\displaystyle d_{\mathrm {H} }(X,Y)=\varepsilon }$

${\displaystyle X\subseteq Y_{\varepsilon }\ {\mbox{and}}\ Y\subseteq X_{\varepsilon }.}$

Por ejemplo, consideremos el espacio métrico de los números reales con la métrica habitual inducida por el valor absoluto, ${\displaystyle \mathbb {R} }$ ${\displaystyle d}$

${\displaystyle d(x,y):=|y-x|,\quad x,y\in \mathbb {R} .}$

Llevar

${\displaystyle X:=(0,1]\quad {\mbox{and}}\quad Y:=[-1,0).}$

Entonces . Sin embargo porque , pero . ${\displaystyle d_{\mathrm {H} }(X,Y)=1\ }$ ${\displaystyle X\nsubseteq Y_{1}}$ ${\displaystyle Y_{1}=[-2,1)\ }$ ${\displaystyle 1\in X}$

Pero es cierto que y  ; en particular es cierto si están cerrados. ${\displaystyle X\subseteq {\overline {Y_{\varepsilon }}}}$ ${\displaystyle Y\subseteq {\overline {X_{\varepsilon }}}}$ ${\displaystyle X,Y}$

Propiedades

• En general, puede ser infinito. Si tanto X como Y están acotados , entonces se garantiza que es finito. ${\displaystyle d_{\mathrm {H} }(X,Y)}$ ${\displaystyle d_{\mathrm {H} }(X,Y)}$
• ${\displaystyle d_{\mathrm {H} }(X,Y)=0}$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 desde X es 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 únicamente 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 , de la siguiente manera: ^[7] ${\displaystyle d(x,y)}$

• Defina una función de distancia entre cualquier punto x de M y cualquier conjunto no vacío Y de M mediante:

${\displaystyle d(x,Y)=\inf\{d(x,y)\mid y\in Y\}.\ }$

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 no vacíos X e Y de M mediante:

${\displaystyle d(X,Y)=\sup\{d(x,Y)\mid x\in X\}.\ }$

Por ejemplo, ${\textstyle d(\{1,7\},\{3,6\})=\sup\{d(1,\{3,6\}),d(7,\{3,6\})\}=\sup\{d(1,3),d(7,6)\}=2.}$

• Si X e Y son compactos, entonces d ( X , Y ) será finito; d ( X , X ) = 0; y d hereda la propiedad de desigualdad triangular 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 (sí 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: ${\displaystyle X\subseteq {\overline {Y}}}$

${\displaystyle d_{\mathrm {H} }(X,Y)=\max\{d(X,Y),d(Y,X)\}\,.}$

Aplicaciones

En visión artificial , la distancia de Hausdorff se puede utilizar para encontrar una plantilla dada 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 da 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 binaria del destino se trata como un conjunto de puntos. A continuación, el algoritmo intenta minimizar la distancia de Hausdorff entre la plantilla y alguna área de la imagen del destino. El área en la imagen del destino con la distancia mínima de Hausdorff a la plantilla, puede considerarse el mejor candidato para ubicar la plantilla en el destino. En gráficos de computadora, la distancia de Hausdorff se utiliza para medir la diferencia entre dos representaciones diferentes del mismo objeto 3D ^[8] particularmente cuando se genera un 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 está alrededor de 2.704,8 km. ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle d_{H}(X,Y)}$

Polo oceánico de inaccesibilidad a 49°01′38″S 123°26′04″O / 49.0273, -123.4345 (Polo oceánico de inaccesibilidad)

Conceptos relacionados

Una medida de la disimilitud de dos formas viene dada por la distancia de Hausdorff hasta la isometría , denotada D _H . 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 ínfimo de d _H ( I ( X ), Y ) entre todas las isometrías I del espacio métrico M consigo mismo. Esta distancia mide lo lejos que están las formas X e Y de ser isométricas.

La convergencia de Gromov-Hausdorff es una idea relacionada: medir la distancia de dos espacios métricos M y N tomando el ínfimo de entre todas las incrustaciones isométricas y en algún espacio métrico común L. ${\displaystyle d_{\mathrm {H} }(I(M),J(N))}$ ${\displaystyle I\colon M\to L}$ ${\displaystyle J\colon N\to L}$

Véase también

• Convergencia de Wijsman
• Convergencia de Kuratowski
• Hemicontinuidad
• Distancia de Fréchet
• Hipertopología

Referencias

1. Rockafellar, R. Tyrrell ; Wets, Roger JB (2005). Análisis variacional . Springer-Verlag. pág. 117. ISBN 3-540-62772-3.
2. 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 , vol. 199, Boston: Kluwer Academic Publishers , págs. 35–39, doi : 10.1007/0-387-33006-2_4 , ISBN 978-0-387-32774-7, Sr.  2249320
3. Munkres, James (1999). Topología (2.ª ed.). Prentice Hall . Págs. 280-281. ISBN. 0-13-181629-2.
4. Diámetro y distancia de Hausdorff, Math.SE
5. Distancia e intersección de Hausdorff, Math.SE
6. Henrikson, Jeff (1999). "Completitud y acotación total de la métrica de Hausdorff" (PDF) . MIT Undergraduate Journal of Mathematics : 69–80. Archivado desde el original (PDF) el 23 de junio de 2002.
7. Barnsley, Michael (1993). Fractales por todas partes . Morgan Kaufmann . Págs. Cap. II.6. ISBN. 0-12-079069-6.
8. Cignoni, P.; Rocchini, C.; Scopigno, R. (1998). "Metro: medición de errores en superficies simplificadas". Computer Graphics Forum . 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 .
• Código MATLAB para la distancia de Hausdorff: [1]