Vietoris-Ripsa Complex

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 februari 2022; kontroller kräver 8 redigeringar .

Vietoris-Rips-komplexet , även kallat Vietoris-komplexet eller Rips-komplexet , är ett sätt att bilda ett topologiskt utrymme från avstånd vid en uppsättning punkter. Detta är ett abstrakt förenklat komplex som kan definieras från vilket metriskt utrymme M och avstånd som helst genom att bilda ett simplex för vilken ändlig uppsättning punkter som helst med en diameter som inte överstiger . Det vill säga, detta är en familj av ändliga delmängder av det metriska rummet M , vilket förstås som en delmängd av kpunkter som en ( k − 1)-dimensionell simplex (en kant för två punkter, en triangel för tre, en tetraeder för fyra, etc.). Om en finit mängd S har egenskapen att avståndet mellan valfritt punkterpar i S inte överstiger , så ingår S som ett simplex i komplexet.

Historik

Vietoris-Rips-komplexet kallades ursprungligen Vietoris-komplexet för att hedra Leopold Vietoris , som introducerade det som ett sätt att utvidga homologiteori från enkla komplex av metriska utrymmen [1] [2] [3] [4] . Efter att Ilya Aronovich Rips använt några komplex för studier av hyperboliska grupper , populariserades deras tillämpningar av Mikhail Leonidovich Gromov [5] , som kallade dem Rips-komplex [3] [4] . Namnet "Vietoris-Rips Complex" tillhör Houseman [3] [4] .

Förhållande med Cech-komplex

Vietoris-Rips-komplexet är nära besläktat med Cech-komplexet (eller nerven ) i uppsättningen av bollar , som har en simplex för vilken ändlig delmängd av bollar som helst med skärningspunkt som inte är noll. I ett geodesiskt konvext utrymme Y , har Vietoris-Rips-komplexet i vilket delrum som helst för ett avstånd samma punkter och kanter som Cech-komplexet av uppsättningen kulor med radie i Y centrerade vid punkter i X . Men till skillnad från Cech-komplexet beror Vietoris-Rips-komplexet för X endast på den inneboende geometrin hos X och inte på någon inbäddning av X i något större utrymme.

Som ett exempel, betrakta ett homogent metriskt utrymme M 3 som består av tre punkter, som var och en är på ett avstånd av en från de andra. Vietoris-Rips-komplexet för M 3 för inkluderar simplexet för alla delmängder av punkter i M ​3 , inklusive triangeln M 3 själv . Om vi ​​bäddar in M ​​3 som en regelbunden triangel i det euklidiska planet , så kommer Cech-komplexet av kulor med radien 1/2 centrerat vid punkterna för M 3 att innehålla alla andra förenklingar av Vietoris-Rips-komplexet, men kommer inte att innehålla en triangel, eftersom det inte finns någon punkt i planet som tillhör alla tre kulorna. Men om M 3 istället är inbäddad i ett metriskt utrymme som innehåller en fjärde punkt på ett avstånd 1/2 från varje punkt i M 3 , kommer Cech-komplexet för bollar med radien 1/2 i detta utrymme att innehålla en triangel. Således beror Cech-komplexet för en fast radie av bollar med mitten M 3 på utrymmet i vilket M 3 kan bäddas in, medan Vietoris-Rips-komplexet förblir oförändrat

Om ett metriskt utrymme X är inbäddat i ett injektivt metriskt utrymme Y , sammanfaller Vietoris-Rips-komplexet för avstånd och mängd X med Cech-komplexet av kulor med radie centrerade vid X i Y . Sålunda är Vietoris-Rips-komplexet för varje metriskt utrymme M lika med Cech-komplexet för ett system av bollar i det injektiva skrovet av utrymmet M .

Koppling med enhetscirkelgrafer och klickkomplex

Vietoris-Rips-komplexet för innehåller en kant för alla par av punkter som är på eller mindre än enhetsavstånd i ett givet metriskt utrymme. Och sedan är dess 1-skelett grafen över enhetscirklar för dess punkter. Den innehåller en simplex för vilken klick som helst i enhetscirkelgrafen, så det är flaggkomplexet (eller klickkomplexet) för enhetscirkelgrafen [6] . Mer allmänt är klickkomplexet för varje graf G Vietoris-Rips-komplexet för ett metriskt utrymme som har G : s hörn som punkter och längden på de kortaste banorna i G som avstånd.

Andra resultat

Om M är ett slutet Riemann-grenrör , så är Vietoris-Rips-komplexet för M eller utrymmen tillräckligt nära M för tillräckligt små värden homotopi ekvivalent med M själv [3] [7] .

Chambers, Erickson och Vora [6] beskrev effektiva algoritmer för att avgöra om en given cykel är sammandragbar i Rips-komplexet av någon ändlig uppsättning i det euklidiska planet .

Applikationer

Liksom i fallet med enhetsdiskdiagram används Vietoris-Rips-komplexet inom datavetenskap för att modellera topologin för trådlösa ad-hoc-nätverk . En av fördelarna med Vietoris-Rips-komplexet i denna applikation är att det bara kan ställas in baserat på avstånden mellan interagerande noder utan att behöva känna till deras fysiska plats. Nackdelen är att, till skillnad från Cech-komplexet, ger Vietoris-Rips-komplexet inte direkt information om hål i kommunikationstäckningen, men denna nackdel kan minskas genom att placera Cech-komplexet mellan två Vietoris-Rips-komplex för olika värden [ 8] [9] . Implementeringen av Vietoris-Rips-komplexen finns i R-paketet TDAstats [10] .

Vietoris-Rips-komplex används också för att markera funktioner i bilder. I denna applikation är komplexet byggt i ett högdimensionellt metriskt utrymme, där punkterna representerar lågordnade bildegenskaper [11] .

Anteckningar

  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 .

Litteratur