Komplex Vietoris-Ripsa

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. února 2022; kontroly vyžadují 8 úprav .

Komplex Vietoris-Rips , nazývaný také komplex Vietoris nebo komplex Rips , je způsob, jak vytvořit topologický prostor ze vzdáleností v množině bodů. Toto je abstraktní simpliciální komplex , který lze definovat z libovolného metrického prostoru M a vzdálenosti vytvořením simplexu pro jakoukoli konečnou množinu bodů s průměrem nepřesahujícím . To znamená, že se jedná o rodinu konečných podmnožin metrického prostoru M , která je chápána jako podmnožina k bodů jako ( k − 1)-rozměrný simplex (hrana pro dva body, trojúhelník pro tři, čtyřstěn pro čtyři atd.). Pokud má konečná množina S tu vlastnost, že vzdálenost mezi libovolným párem bodů v S nepřesahuje , pak je S zahrnuta jako simplex v komplexu.

Historie

Komplex Vietoris–Rips byl původně nazýván komplexem Vietoris na počest Leopolda Vietorise , který jej zavedl jako prostředek k rozšíření teorie homologie ze simpliciálních komplexů metrických prostorů [1] [2] [3] [4] . Poté , co Ilja Aronovič Rips použil některé komplexy pro studium hyperbolických grup , jejich aplikace zpopularizoval Michail Leonidovič Gromov [5] , který je nazval Ripsovy komplexy [3] [4] . Název "Vietoris-Rips Complex" patří Housemanovi [3] [4] .

Vztah s českými komplexy

Komplex Vietoris–Rips úzce souvisí s Cechovým komplexem (neboli nervem ) množiny kuliček , který má simplex pro jakoukoli konečnou podmnožinu kuliček s nenulovým průnikem. V geodeticky konvexním prostoru Y má Vietoris-Ripsův komplex libovolného podprostoru pro vzdálenost stejné body a hrany jako Cechův komplex množiny kuliček o poloměru v Y se středem v bodech v X . Na rozdíl od Cechova komplexu však Vietoris-Ripsův komplex pro X závisí pouze na vnitřní geometrii X , a ne na nějakém vnoření X do nějakého většího prostoru.

Jako příklad uvažujme homogenní metrický prostor M 3 sestávající ze tří bodů, z nichž každý je ve vzdálenosti jednoho od ostatních. Komplex Vietoris-Rips pro M 3 for zahrnuje simplex pro jakoukoli podmnožinu bodů v M ​​3 , včetně samotného trojúhelníku M 3 . Pokud vložíme M 3 jako pravidelný trojúhelník do euklidovské roviny , pak Cechův komplex kuliček o poloměru 1/2 se středem v bodech M 3 bude obsahovat všechny ostatní zjednodušení Vietoris-Ripsova komplexu, ale nebude obsahovat trojúhelník, protože v rovině není žádný bod, který by patřil všem třem koulím. Pokud je však M 3 místo toho zasazena do metrického prostoru, který obsahuje čtvrtý bod ve vzdálenosti 1/2 od každého bodu M 3 , bude Cechův komplex pro koule o poloměru 1/2 v tomto prostoru obsahovat trojúhelník. Cechův komplex pro pevný poloměr kuliček se středy M 3 tedy závisí na prostoru, do kterého lze M 3 zapustit, zatímco Vietoris-Ripsův komplex zůstává nezměněn.

Pokud je metrický prostor X vložen do injektivního metrického prostoru Y , Vietoris-Ripsův komplex pro vzdálenost a množinu X se shoduje s Cechovým komplexem kuliček o poloměru se středem v X v Y . Vietoris-Ripsův komplex libovolného metrického prostoru M se tedy rovná Čechovu komplexu systému kuliček v injektivním trupu prostoru M .

Spojení s jednotkovými kruhovými grafy a klikovými komplexy

Komplex Vietoris-Rips obsahuje hranu pro jakýkoli pár bodů, které jsou v daném metrickém prostoru v jednotkové vzdálenosti nebo menší. A pak jeho 1-kostra je graf jednotkových kružnic jeho bodů. Obsahuje simplex pro libovolnou kliku v jednotkovém kruhovém grafu, jedná se tedy o příznakový komplex (nebo klikový komplex) jednotkového kruhového grafu [6] . Obecněji, klikový komplex jakéhokoli grafu G je Vietoris-Ripsův komplex pro metrický prostor, který má vrcholy G jako body a délky nejkratších cest v G jako vzdálenost.

Další výsledky

Jestliže M je uzavřená Riemannovská varieta , pak pro dostatečně malé hodnoty je Vietoris-Ripsův komplex pro M nebo prostory dostatečně blízké M homotopické ekvivalentní samotnému M [3] [7] .

Chambers, Erickson a Vora [6] popsali účinné algoritmy pro určení, zda je daný cyklus kontrahovatelný v Ripsově komplexu jakékoli konečné množiny v euklidovské rovině .

Aplikace

Stejně jako v případě jednotkových diskových grafů se komplex Vietoris-Rips používá v informatice k modelování topologie bezdrátových ad-hoc sítí . Jednou z výhod komplexu Vietoris-Rips v této aplikaci je, že jej lze nastavit pouze na základě vzdáleností mezi interagujícími uzly bez nutnosti znát jejich fyzickou polohu. Nevýhodou je, že na rozdíl od komplexu Cech neposkytuje komplex Vietoris-Rips přímo informace o dírách v komunikačním pokrytí, ale tuto nevýhodu lze snížit umístěním komplexu Cech mezi dva komplexy Vietoris-Rips pro různé hodnoty [ 8] [9] . Implementaci komplexů Vietoris-Rips lze nalézt v R balíčku TDAstats [10] .

Komplexy Vietoris-Rips se také používají ke zvýraznění prvků na snímcích. V této aplikaci je komplex postaven ve vysokorozměrném metrickém prostoru, ve kterém body představují obrazové prvky nízkého řádu [11] .

Poznámky

  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 .

Literatura