distancia de Hausdorff

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 . ${\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 mínimo 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, deje ${\displaystyle X\subset M,}$

$${\displaystyle X_{\varepsilon }:=\bigcup _{x\in X}\{z\in M\mid d(z,x)\leq \varepsilon \},}$$

bola ${\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 }\}.}$$

De manera equivalente, ^[1]

$${\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 implica ${\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, considere 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 , se garantiza que serán finitos. ${\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 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] ${\displaystyle d(x,y)}$

• Defina una función de distancia entre cualquier punto x de M y cualquier conjunto Y de M no vacío 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 cualesquiera 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 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: ${\displaystyle X\subseteq Y}$

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

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. ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle d_{H}(X,Y)}$

Polo oceánico de inaccesibilidad en 49°01′38″S 123°26′04″W / 49.0273°S 123.4345°W / -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 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. ${\displaystyle d_{\mathrm {H} }(I(M),J(N))}$ ${\displaystyle I\colon M\to L}$ ${\displaystyle J\colon N\to L}$

Ver también

• Convergencia de Wijsman
• Convergencia de Kuratowski
• hemicontinuidad
• distancia de frechet

Referencias

1. Rockafellar, R. Tyrrell ; Mojados, Roger JB (2005). Análisis variacional . Springer-Verlag. pag. 117.ISBN​ 3-540-62772-3.
2. 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 , ISBN 978-0-387-32774-7, señor  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). "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.
7. Barnsley, Michael (1993). Fractales por todas partes . Morgan Kaufman . págs. II.6. ISBN 0-12-079069-6.
8. 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 .
• Código MATLAB para la distancia de Hausdorff: [1]