En topología , 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. Es un complejo simplicial abstracto que se puede definir a partir de cualquier espacio métrico M y distancia δ formando un simplex para cada conjunto finito de puntos que tenga un diámetro como máximo δ. Es decir, es una familia de subconjuntos finitos de M , en la que pensamos que un subconjunto de k puntos forma una ( k - 1) simplex dimensional (una arista para dos puntos, un triángulo para tres puntos, un tetraedro para cuatro puntos, etc.); si un conjunto finito S tiene la propiedad de que la distancia entre cada par de puntos en S es como máximo δ, entonces incluimos S como un simplex en el complejo.
Historia
El complejo de Vietoris-Rips se llamó originalmente el complejo de Vietoris, por Leopold Vietoris , quien lo introdujo como un medio para extender la teoría de la homología de los complejos simpliciales a los espacios métricos. [1] Después de que Eliyahu Rips aplicara el mismo complejo al estudio de grupos hiperbólicos , su uso fue popularizado por Mikhail Gromov ( 1987 ), quien lo llamó el complejo Rips. [2] El nombre "complejo Vietoris-Rips" se debe a Jean-Claude Hausmann ( 1995 ). [3]
Relación con el complejo Čech
El complejo Vietoris-Rips está estrechamente relacionado con el complejo Čech (o nervio ) de un conjunto de bolas , que tiene un simplex para cada subconjunto finito de bolas con intersección no vacía. En un espacio Y geodésicamente convexo , el complejo Vietoris-Rips de cualquier subespacio X ⊂ Y para la distancia δ tiene los mismos puntos y bordes que el complejo Čech del conjunto de bolas de radio δ / 2 en Y que están centradas en los puntos de X . Sin embargo, a diferencia del complejo Čech, el complejo Vietoris-Rips de X depende solo de la geometría intrínseca de X , y no de ninguna incrustación de X en un espacio más grande.
Como ejemplo, considere el espacio métrico uniforme M 3 que consta de tres puntos, cada uno a una distancia unitaria entre sí. El complejo Vietoris-Rips de M 3 , para δ = 1, incluye un simplex para cada subconjunto de puntos en M 3 , incluido un triángulo para el propio M 3 . Si incrustamos M 3 como un triángulo equilátero en el plano euclidiano , entonces el complejo Čech de las bolas de radio-1/2 centradas en los puntos de M 3 contendría todos los demás símplex del complejo Vietoris-Rips pero no este triángulo , ya que no hay ningún punto del plano contenido en 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 uno de los tres puntos de M 3 , el complejo Čech de las bolas de radio 1/2 en este espacio contendría el triángulo . Por lo tanto, el complejo de Čech de bolas de radio fijo centradas en M 3 difiere según el espacio más grande en el que se pueda incrustar M 3 , mientras que el complejo Vietoris-Rips permanece sin cambios.
Si cualquier espacio métrico X está incrustado en un espacio métrico inyectiva Y , los Vietoris-Rips complejo para delta distancia y X coincide con el Čech complejos de las bolas de radio δ / 2 centradas en los puntos de X en Y . Por lo tanto, los Vietoris-Rips compleja de cualquier espacio métrico M es igual a la Čech complejo de un sistema de bolas en el tramo estrecho de M .
Relación con los gráficos de discos unitarios y los complejos de camarillas
El complejo de Vietoris-Rips para δ = 1 contiene un borde para cada par de puntos que están a una distancia unitaria o menos en el espacio métrico dado. Como tal, su 1- esqueleto es el gráfico de disco unitario de sus puntos. Contiene un simplex para cada camarilla en el gráfico de disco unitario, por lo que es el complejo de camarilla o el complejo de bandera del gráfico de disco unitario. [4] Más generalmente, la camarilla complejo de cualquier gráfico G es un Vietoris-Rips complejo para el espacio métrico que tiene como puntos de los vértices de G y que tiene como sus distancias las longitudes de los caminos más cortos en G .
Otros resultados
Si M es una variedad Riemanniana cerrada , entonces, para valores suficientemente pequeños de δ, el complejo de Vietoris-Rips de M , o de espacios suficientemente cercanos a M , es homotopía equivalente a M mismo. [5]
Chambers, Erickson y Worah (2008) describen algoritmos eficientes para determinar si un ciclo dado es contráctil en el complejo de Rips de cualquier conjunto de puntos finitos en el plano euclidiano .
Aplicaciones
Al igual que con los gráficos de discos unitarios, el complejo Vietoris-Rips se ha aplicado en informática para modelar la topología de redes de comunicación inalámbrica ad hoc . Una ventaja del complejo Vietoris-Rips en esta aplicación es que se puede determinar solo a partir de las distancias entre los nodos de comunicación, sin tener que inferir sus ubicaciones físicas exactas. Una desventaja es que, a diferencia del complejo Čech, el complejo Vietoris-Rips no proporciona directamente información sobre las lagunas en la cobertura de comunicación, pero esta falla puede mejorarse intercalando el complejo Čech entre dos complejos Vietoris-Rips para diferentes valores de δ. [6] Una implementación de complejos Vietoris-Rips se puede encontrar en el TDAstats paquete R . [7]
Los complejos de Vietoris-Rips también se han aplicado para la extracción de características en datos de imágenes digitales; en esta aplicación, el complejo se construye a partir de un espacio métrico de alta dimensión en el que los puntos representan características de imagen de bajo nivel. [8]
Notas
- ↑ Vietoris (1927) ; Lefschetz (1942) ; Hausmann (1995) ; Reitberger (2002) .
- ^ Hausmann (1995) ; Reitberger (2002) .
- ^ Reitberger (2002) .
- ^ Cámaras, Erickson y Worah (2008) .
- ^ Hausmann (1995) , Latschev (2001) .
- ↑ de Silva y Ghrist (2006) , Muhammad y Jadbabaie (2007) .
- ^ Wadhwa y col. 2018 .
- ^ Carlsson, Carlsson y de Silva (2006) .
Referencias
- Carlsson, Erik; Carlsson, Gunnar ; de Silva, Vin (2006), "Un método topológico algebraico para la identificación de características" (PDF) , International Journal of Computational Geometry and Applications , 16 (4): 291–314, doi : 10.1142 / S021819590600204X , archivado desde el original (PDF ) el 2019-03-04.
- Chambers, Erin W .; Erickson, Jeff; Worah, Pratik (2008), "Testing contractibility in planar Rips complexes" , Actas del 24º Simposio anual de ACM sobre geometría computacional , págs. 251-259, CiteSeerX 10.1.1.296.6424 , doi : 10.1145 / 1377676.1377721.
- Chazal, Frédéric; Oudot, Steve (2008), "Towards Persistence-Based Reconstruction in Euclidean Spaces", Simposio ACM sobre geometría computacional : 232–241, arXiv : 0712.2638 , doi : 10.1145 / 1377676.1377719 , ISBN 978-1-60558-071-5.
- de Silva, Vin; Ghrist, Robert (2006), "Cobertura sin coordenadas en redes de sensores con límites controlados mediante homología", The International Journal of Robotics Research , 25 (12): 1205-1222, doi : 10.1177 / 0278364906072252.
- Gromov, Mikhail (1987), "Grupos hiperbólicos", Ensayos en teoría de grupos , Publicaciones del Instituto de Investigación de Ciencias Matemáticas , 8 , Springer-Verlag, págs. 75-263.
- Hausmann, Jean-Claude (1995), "Sobre los complejos Vietoris-Rips y una teoría de cohomología para espacios métricos", Perspectivas en topología: Actas de una conferencia en honor de William Browder , Annals of Mathematics Studies, 138 , Princeton University Press , págs. 175-188, MR 1368659.
- Latschev, Janko (2001), "Vietoris-Rips complejos de espacios métricos cerca de una variedad Riemanniana cerrada", Archiv der Mathematik , 77 (6): 522–528, doi : 10.1007 / PL00000526 , MR 1879057.
- Lefschetz, Solomon (1942), Topología algebraica , Nueva York: Amer. Matemáticas. Soc., Pág. 271, MR 0007093.
- Muhammad, A .; Jadbabaie, A. (2007), "Verificación de cobertura dinámica en redes de sensores móviles a través de laplacianos conmutados de orden superior" (PDF) , en Broch, Oliver (ed.), Robotics: Science and Systems , MIT Press.
- Reitberger, Heinrich (2002), "Leopold Vietoris (1891-2002)" (PDF) , Notices of the American Mathematical Society , 49 (20).
- Vietoris, Leopold (1927), "Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen", Mathematische Annalen , 97 (1): 454–472, doi : 10.1007 / BF01447877.
- Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob (2018), "TDAstats: canalización R para calcular la homología persistente en el análisis de datos topológicos" , Journal of Open Source Software , 3 (28): 860, doi : 10.21105 / joss.00860