Vietoris-Ripsa kompleksi

Vietoris-Rips-kompleksi , jota kutsutaan myös Vietoris-kompleksiksi tai Rips-kompleksiksi , on tapa muodostaa topologinen avaruus etäisyyksistä tietyissä pisteissä. Tämä on abstrakti yksinkertainen kompleksi , joka voidaan määrittää mistä tahansa metriavaruudesta M ja etäisyydestä muodostamalla simpleksi mille tahansa äärelliselle pistejoukolle , jonka halkaisija ei ole suurempi kuin . Toisin sanoen tämä on metriavaruuden M äärellisten osajoukkojen perhe , joka ymmärretään k pisteen osajoukoksi ( k − 1)-ulotteisena simpleksinä (reuna kahdelle pisteelle, kolmio kolmelle, tetraedri neljä jne.). Jos äärellisellä joukolla S on ominaisuus, että minkään S :n pisteparin välinen etäisyys ei ylitä , niin S sisällytetään kompleksina simpleksinä.

Historia

Vietoris-Rips-kompleksia kutsuttiin alun perin Vietoris-kompleksiksi Leopold Vietorisin kunniaksi , joka esitteli sen keinona laajentaa homologiateoriaa yksinkertaisista metristen avaruuksien komplekseista [1] [2] [3] [4] . Sen jälkeen kun Ilja Aronovitš Rips käytti joitain komplekseja hyperbolisten ryhmien tutkimiseen, Mihail Leonidovich Gromov [5] suositti niiden sovelluksia ja kutsui niitä Rips-komplekseiksi [3] [4] . Nimi "Vietoris-Rips Complex" kuuluu Housemanille [3] [4] .

Suhde Cech-kompleksien kanssa

Vietoris–Rips-kompleksi liittyy läheisesti pallojoukon Cech-kompleksiin (tai hermoon ) , jolla on simpleksi mille tahansa äärelliselle pallojen osajoukolle, jonka leikkauspiste on nollasta poikkeava . Geodeettisesti konveksissa avaruudessa Y minkä tahansa etäisyyden aliavaruuden Vietoris-Rips-kompleksilla on samat pisteet ja reunat kuin Y :n säteisten pallojen joukon Cech-kompleksilla, jonka keskipiste on X :n pisteisiin . Kuitenkin, toisin kuin Cech-kompleksi, Vietoris-Rips-kompleksi X :lle riippuu vain X:n sisäisestä geometriasta , ei X :n upottamisesta johonkin suurempaan tilaan.

Tarkastellaan esimerkkinä homogeenistä metriavaruutta M 3 , joka koostuu kolmesta pisteestä, joista jokainen on yhden etäisyydellä muista. Vietoris-Rips-kompleksi kohteelle M 3 sisältää simplexin mille tahansa M 3 : n pisteiden osajoukolle , mukaan lukien itse kolmio M 3 . Jos upotamme M 3 : n säännöllisenä kolmiona euklidiseen tasoon , niin Cech-kompleksi palloista, joiden säde on 1/2 ja joiden keskipiste on M 3 :n pisteitä, sisältää kaikki muut Vietoris-Rips-kompleksin yksinkertaisuudet, mutta ei sisällä kolmio, koska tasossa ei ole pistettä, joka kuuluisi kaikille kolmelle pallolle. Jos M 3 kuitenkin upotetaan sen sijaan metriseen avaruuteen, joka sisältää neljännen pisteen etäisyydellä 1/2 kustakin M 3 :n pisteestä, Cech-kompleksi palloille, joiden säde on 1/2 tässä tilassa, sisältää kolmion. Siten Cech-kompleksi kiinteälle säteelle palloille, joiden keskipisteet ovat M 3 , riippuu tilasta, johon M 3 voidaan upottaa, kun taas Vietoris-Rips -kompleksi pysyy muuttumattomana

Jos metriavaruus X on upotettu injektiiviseen metriseen avaruuteen Y , Vietoris-Rips-kompleksi etäisyydelle ja joukolle X osuu yhteen säteisten pallojen Cech-kompleksin kanssa, jonka keskipiste on X :ssä Y . Siten minkä tahansa metrisen avaruuden M Vietoris-Rips-kompleksi on yhtä suuri kuin tilan M injektiokungossa olevan pallojärjestelmän Cech-kompleksi .

Yhteys yksikköympyräkaavioiden ja klikkikompleksien kanssa

Vietoris-Rips-kompleksi for sisältää reunan mille tahansa pisteparille, joka on yksikköetäisyydellä tai sitä pienemmällä etäisyydellä tietyssä metriavaruudessa. Ja sitten sen 1-luuranko on sen pisteiden yksikköympyröiden kuvaaja . Se sisältää simpleksin mille tahansa yksikköympyräkaavion klikkille, joten se on yksikköympyräkaavion lippukompleksi ( tai klikkikompleksi) [6] . Yleisemmin minkä tahansa graafin G klikkikompleksi on Vietoris-Rips-kompleksi metriselle avaruudelle, jonka G:n kärjet ovat pisteitä ja G : n lyhimpien polkujen pituudet etäisyytenä.

Muut tulokset

Jos M on suljettu Riemannin monisto , niin riittävän pienillä arvoilla Vietoris-Rips-kompleksi M :lle tai riittävän lähellä M :tä olevat avaruudet ovat homotopiaa ekvivalentteja itse M :lle [3] [7] .

Chambers, Erickson ja Vora [6] kuvasivat tehokkaita algoritmeja sen määrittämiseksi, onko tietty sykli supistuva minkä tahansa euklidisen tason äärellisen joukon Rips-kompleksissa .

Sovellukset

Kuten yksikkölevykaavioiden tapauksessa, Vietoris-Rips-kompleksia käytetään tietojenkäsittelytieteessä langattomien ad-hoc-verkkojen topologian mallintamiseen . Yksi Vietoris-Rips-kompleksin eduista tässä sovelluksessa on, että se voidaan asettaa vain vuorovaikutuksessa olevien solmujen välisten etäisyyksien perusteella ilman, että tarvitsee tietää niiden fyysistä sijaintia. Haittapuolena on se, että toisin kuin Cech-kompleksi, Vietoris-Rips-kompleksi ei anna suoraan tietoa tiedonsiirron kattavuudesta, mutta tätä haittaa voidaan vähentää sijoittamalla Cech-kompleksi kahden Vietoris-Rips-kompleksin väliin eri arvoilla [ 8] [9] . Vietoris-Rips-kompleksien toteutus löytyy R-paketista TDAstats [10] .

Vietoris-Rips-komplekseja käytetään myös kuvien ominaisuuksien korostamiseen. Tässä sovelluksessa kompleksi on rakennettu korkeadimensionaaliseen metriseen avaruuteen, jossa pisteet edustavat matalan kertaluokan kuvan ominaisuuksia [11] .

Muistiinpanot

1. ↑ Vietoris, 1927 .
2. ↑ Lefschetz, 1942 .
3. ↑ 1 2 3 4 Hausmann, 1995 .
4. ↑ 1 2 3 Reitberger, 2002 .
5. ↑ Gromov, 1987 .
6. ↑ 12 Chambers, 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 .

Kirjallisuus

• Erik Carlsson, Gunnar Carlsson, Vin de Silva. Algebrallinen topologinen menetelmä piirteiden tunnistamiseen  // International Journal of Computational Geometry and Applications . - 2006. - T. 16 , no. 4 . — S. 291–314 . - doi : 10.1142/S021819590600204X .
• Erin W. Chambers, Jeff Erickson, Pratik Worah. Supistettavuuden testaus tasomaisissa Rips-komplekseissa // Proceedings of the 24th Annual ACM Symposium on Computational Geometry. - 2008. - S. 251-259. - doi : 10.1145/1377676.1377721 .
• Frederic Chazal, Steve Oudot. Kohti pysyvyyteen perustuvaa rekonstruktiota euklidisissa tiloissa // ACM Symposium on Computational Geometry. - 2008. - S. 232-241 . - ISBN 978-1-60558-071-5 . - doi : 10.1145/1377676.1377719 . - arXiv : 0712.2638 .
• Vin de Silva, Robert Ghrist. Koordinaattivapaa kattavuus anturiverkoissa, joissa on valvotut rajat homologian kautta  // The International Journal of Robotics Research. - 2006. - T. 25 . — S. 1205–1222 . - doi : 10.1177/0278364906072252 .
• Mihail Leonidovich Gromov. Hyperboliset ryhmät // Ryhmäteorian esseitä. - Springer-Verlag, 1987. - T. 8. - S. 75–263. — ( Matematiikan tutkimuslaitoksen julkaisut).
• Jean Claude Hausmann. Vietoris-Rips-komplekseista ja metristen avaruuksien kohemologiateoriasta // Topologian näkymät: William Browderin kunniaksi järjestetyn konferenssin julkaisut. - Princeton University Press , 1995. - V. 138. - S. 175-188. — (Matematiikan opintojen päiväkirjat). .
• Janko Latschev. Vietoris-Ripsin metristen avaruuksien kompleksit lähellä suljettua Riemannin monistoa // Archiv der Mathematik. - 2001. - T. 77 , no. 6 . — S. 522–528 . - doi : 10.1007/PL00000526 .
• Solomon Lefschetz. Algebrallinen topologia. - New York: Amerikka. Matematiikka. Soc., 1942. - S. 271.
• Muhammad A., Jadbabaie A. Dynaaminen peiton todentaminen mobiilianturiverkoissa kytketyn korkeamman asteen laplalaisten kautta // Robotics: Science and Systems / toimittaja: Oliver Broch. – MIT Press, 2007.
• Heinrich Reitberger. Leopold Vietoris (1891–2002)  // Notices of the American Mathematical Society . - 2002. - T. 49 , no. 20 .
• Leopold Vietoris. Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen // Mathematische Annalen . - 1927. - T. 97 , no. 1 . — S. 454–472 . - doi : 10.1007/BF01447877 .
• Raoul Wadhwa, Drew Williamson, Andrew Dhawan, Jacob Scott. TDAstats: R-putkisto pysyvän homologian laskemiseen topologisessa data-analyysissä  // Journal of Open Source Software. - 2018. - Osa 3 , no. 28 . - S. 860 . - doi : 10.21105/joss.00860 .