distancia de Hausdorff

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 independiente. Recibe su nombre de Felix Hausdorff y Dimitrie Pompeiu .

De manera informal, dos conjuntos están cerca en la distancia de Hausdorff si cada punto de un conjunto está cerca de algún punto del otro. La distancia de Hausdorff es la distancia máxima que un adversario puede obligar a recorrer a alguien eligiendo un punto en uno de los dos conjuntos, desde donde debe desplazarse al otro. En otras palabras, es la mayor de todas las distancias entre un punto de un conjunto y el punto más cercano del otro.

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${\displaystyle [0,1]\to \mathbb {R} ^{3}}$.

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

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

dónde${\textstyle \operatorname {sup} }$representa el operador supremo ,${\textstyle d(a,B):=\displaystyle \inf _{b\in B}d(a,b)}$cuantifica la distancia desde un punto${\textstyle a\in X}$al subconjunto${\textstyle B\subsetq X}$, y${\estilo de texto \nombre del operador {inf} }$es el operador ínfimo .

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

De forma equivalente, ^{[ 1 ]}$${\displaystyle {\begin{aligned}d_{\mathrm {H} }(X,Y)&=\sup _{w\in M}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|\\[6px]&=\sup _{w\in X\cup Y}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|\\[6px]&=\sup _{w\in M}{\bigl |}d(w,X)-d(w,Y){\bigr |},\end{aligned}}}$$

dónde${\textstyle d(w,X):=\displaystyle \inf _{x\in X}d(w,x)}$es la distancia más pequeña desde el punto${\displaystyle w}$al conjunto${\displaystyle X}$.

• En general,${\displaystyle d_{\text{H}}(X,Y)}$puede ser infinito. Si tanto X como Y están acotados , entonces${\displaystyle d_{\text{H}}(X,Y)}$Se garantiza que será finito.
• ${\displaystyle d_{\text{H}}(X,Y)=0}$si y solo si X e Y tienen el mismo cierre.
• Para cada punto x de M y cualesquiera conjuntos no vacíos Y , Z de M : d ( x , Y ) ≤ d ( x , Z ) + dH ( 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 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 F ( M ) también lo es. ^{[ 6 ]}
  • Si M es compacto, entonces F ( M también lo es ).
  • La topología de F ( M ) depende únicamente de la topología de M , no de la métrica d .

La definición de la distancia de Hausdorff se puede derivar mediante una serie de extensiones naturales de la función de distancia.${\displaystyle d(x,y)}$en el espacio métrico subyacente M , como sigue: ^{[ 7 ]}

• Definimos 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.
• Definimos una función de "distancia" (no necesariamente simétrica) entre dos conjuntos no vacíos cualesquiera X e Y de M mediante$${\displaystyle d(X,Y)=\sup\{d(x,Y)\mid x\in X\}.}$$Por ejemplo,${\displaystyle 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      ${\displaystyle X\subseteq {\overline {Y}}}$). 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 d_{\text{H}}(X,Y)=\max\{d(X,Y),d(Y,X)\}.}$$

En visión artificial , la distancia de Hausdorff se puede utilizar para encontrar una plantilla dada en una imagen objetivo arbitraria. La plantilla y la imagen suelen preprocesarse mediante un detector de bordes, lo que da como resultado 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. El algoritmo entonces intenta minimizar la distancia de Hausdorff entre la plantilla y un área de la imagen objetivo. El área en la imagen objetivo con la distancia de Hausdorff mínima a la plantilla puede considerarse la mejor candidata para localizar 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 al generar el nivel de detalle para la visualización eficiente de modelos 3D complejos.

Si${\displaystyle X}$es la superficie de la Tierra, y${\displaystyle Y}$es la superficie terrestre de la Tierra, entonces al encontrar el punto Nemo , vemos${\displaystyle d_{\text{H}}(X,Y)}$son aproximadamente 2.704,8  km.

Una medida de la disimilitud entre dos figuras 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 (generalmente 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 cuán lejos están las figuras 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${\displaystyle d_{\text{H}}{\big (}I(M),J(N){\big )}}$entre todas las incrustaciones isométricas${\displaystyle I\colon M\to L}$y${\displaystyle J\colon N\to L}$en algún espacio métrico común L.

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

• 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: