Complejo Vietoris-Ripsa

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 10 de febrero de 2022; las comprobaciones requieren 8 ediciones .

El complejo Vietoris-Rips , también llamado complejo Vietoris o complejo Rips , es una forma de formar un espacio topológico a partir de distancias en un conjunto de puntos. Este es un complejo simplicial abstracto que se puede definir a partir de cualquier espacio métrico M y distancia formando un símplex para cualquier conjunto finito de puntos con un diámetro que no exceda . Es decir, esta es una familia de subconjuntos finitos del espacio métrico M , que se entiende como un subconjunto de kpuntos como un símplex ( k − 1)-dimensional (una arista para dos puntos, un triángulo para tres, un tetraedro para cuatro, etc.). Si un conjunto finito S tiene la propiedad de que la distancia entre cualquier par de puntos en S no excede , entonces S se incluye como simplex en el complejo.

Historia

El complejo de Vietoris-Rips se llamó originalmente complejo de Vietoris en honor a Leopold Vietoris , quien lo introdujo como un medio para extender la teoría de la homología a partir de complejos simpliciales de espacios métricos [1] [2] [3] [4] . Después de que Ilya Aronovich Rips usara algunos complejos para el estudio de los grupos hiperbólicos , sus aplicaciones fueron popularizadas por Mikhail Leonidovich Gromov [5] , quien los llamó complejos de Rips [3] [4] . El nombre "Vietoris-Rips Complex" pertenece a Houseman [3] [4] .

Relación con los complejos de Cech

El complejo Vietoris-Rips está estrechamente relacionado con el complejo Cech (o nervio ) del conjunto de bolas , que tiene un símplex para cualquier subconjunto finito de bolas con intersección distinta de cero. En un espacio geodésicamente convexo Y , el complejo Vietoris-Rips de cualquier subespacio para una distancia tiene los mismos puntos y aristas que el complejo Cech del conjunto de bolas de radio en Y centradas en puntos en X . Sin embargo, a diferencia del complejo de Cech, el complejo de Vietoris-Rips para X depende solo de la geometría intrínseca de X y no de ninguna incrustación de X en un espacio mayor.

Como ejemplo, considere un espacio métrico homogéneo M 3 que consta de tres puntos, cada uno de los cuales está a una distancia de los demás. El complejo de Vietoris-Rips para M 3 incluye el símplex para cualquier subconjunto de puntos en M 3 , incluido el propio triángulo M 3 . Si incrustamos M 3 como un triángulo regular en el plano euclidiano , entonces el complejo Cech de bolas de radio 1/2 con centro en los puntos de M 3 contendrá todos los demás simples del complejo Vietoris-Rips, pero no contendrá un triángulo, ya que no hay ningún punto en el plano que pertenezca a las tres bolas. Sin embargo, si M 3 está incrustado en un espacio métrico que contiene un cuarto punto a una distancia de 1/2 de cada punto de M 3 , el complejo de Cech para bolas de radio 1/2 en este espacio contendrá un triángulo. Por lo tanto, el complejo de Cech para un radio fijo de bolas con centros M 3 depende del espacio en el que se puede incrustar M 3 , mientras que el complejo de Vietoris-Rips permanece sin cambios.

Si un espacio métrico X está incrustado en un espacio métrico inyectivo Y , el complejo Vietoris-Rips para la distancia y el conjunto X coincide con el complejo Cech de bolas de radio con centro en X en Y. Así, el complejo de Vietoris-Rips de cualquier espacio métrico M es igual al complejo de Cech de un sistema de bolas en la envolvente inyectiva del espacio M .

Conexión con gráficos de círculo unitario y complejos de camarilla

El complejo de Vietoris-Rips para contiene una arista para cualquier par de puntos que estén a una distancia unitaria o menor en un espacio métrico dado. Y luego su 1-esqueleto es la gráfica de círculos unitarios de sus puntos. Contiene un símplex para cualquier camarilla en el gráfico de círculo unitario, por lo que es el complejo de banderas (o complejo de camarilla) del gráfico de círculo unitario [6] . De manera más general, el complejo clique de cualquier gráfico G es el complejo Vietoris-Rips para un espacio métrico que tiene los vértices de G como puntos y las longitudes de los caminos más cortos en G como distancia.

Otros resultados

Si M es una variedad de Riemann cerrada , entonces, para valores suficientemente pequeños, el complejo de Vietoris-Rips para M o espacios suficientemente cercanos a M son equivalentes homotópicos a M mismo [3] [7] .

Chambers, Erickson y Vora [6] describieron algoritmos eficientes para determinar si un ciclo dado es contráctil en el complejo Rips de cualquier conjunto finito en el plano euclidiano .

Aplicaciones

Como en el caso de los gráficos de unidades de disco, el complejo Vietoris-Rips se utiliza en informática para modelar la topología de las redes inalámbricas ad-hoc . Una de las ventajas del complejo Vietoris-Rips en esta aplicación es que se puede configurar basándose únicamente en las distancias entre los nodos que interactúan sin necesidad de conocer su ubicación física. La desventaja es que, a diferencia del complejo Cech, el complejo Vietoris-Rips no brinda información directamente sobre los agujeros en la cobertura de comunicación, pero esta desventaja se puede reducir colocando el complejo Cech entre dos complejos Vietoris-Rips para diferentes valores [ 8] [9] . La implementación de los complejos Vietoris-Rips se puede encontrar en el paquete R TDAstats [10] .

Los complejos Vietoris-Rips también se utilizan para resaltar características en las imágenes. En esta aplicación, el complejo se construye en un espacio métrico de alta dimensión, en el que los puntos representan características de imagen de bajo orden [11] .

Notas

  1. ↑ Vietoris, 1927 .
  2. ↑ Lefschetz, 1942 .
  3. ↑ 1 2 3 4 Hausmann, 1995 .
  4. ↑ 1 2 3 Reitberger, 2002 .
  5. ↑ Gromov, 1987 .
  6. ↑ 12 cámaras, Erickson, Worah, 2008 .
  7. ↑ Latschev, 2001 .
  8. ↑ de Silva, Ghrist, 2006 .
  9. ↑ Muhammad, Jadbabaie, 2007 .
  10. ↑ Wadhwa, Williamson, Dhawan, Scott, 2018 .
  11. ↑ Carlsson, Carlsson, de Silva, 2006 .

Literatura