Complexul Vietoris-Ripsa

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 10 februarie 2022; verificările necesită 8 modificări .

Complexul Vietoris-Rips , numit și complexul Vietoris sau complexul Rips , este o modalitate de a forma un spațiu topologic de la distanțe la un set de puncte. Acesta este un complex simplist abstract care poate fi definit din orice spațiu metric M și distanță prin formarea unui simplex pentru orice set finit de puncte cu diametrul care nu depășește . Adică, aceasta este o familie de submulțimi finite ale spațiului metric M , care este înțeleasă ca o submulțime de k puncte ca un simplex ( k − 1)-dimensional (o muchie pentru două puncte, un triunghi pentru trei, un tetraedru pentru patru etc.). Dacă o mulțime finită S are proprietatea că distanța dintre orice pereche de puncte din S nu depășește , atunci S este inclus ca simplex în complex.

Istorie

Complexul Vietoris-Rips a fost numit inițial complexul Vietoris în onoarea lui Leopold Vietoris , care l-a introdus ca mijloc de extindere a teoriei omologiei de la complexe simpliale de spații metrice [1] [2] [3] [4] . După ce Ilya Aronovich Rips a folosit unele complexe pentru studiul grupurilor hiperbolice , aplicațiile lor au fost popularizate de Mihail Leonidovici Gromov [5] , care le-a numit complexe Rips [3] [4] . Denumirea „Vietoris-Rips Complex” îi aparține lui Houseman [3] [4] .

Relația cu complexele Cech

Complexul Vietoris-Rips este strâns legat de complexul Cech (sau nervul ) al setului de bile , care are un simplex pentru orice subset finit de bile cu intersecție diferită de zero. Într -un spațiu geodezic convex Y , complexul Vietoris-Rips al oricărui subspațiu pentru o distanță are aceleași puncte și margini ca și complexul Cech al mulțimii de bile cu raza din Y centrate în puncte din X . Totuși, spre deosebire de complexul Cech, complexul Vietoris-Rips pentru X depinde doar de geometria intrinsecă a lui X și nu de orice încorporare a lui X într-un spațiu mai mare.

Ca exemplu, luăm în considerare un spațiu metric omogen M 3 format din trei puncte, fiecare dintre ele fiind la o distanță de unul de celelalte. Complexul Vietoris-Rips pentru M 3 pentru include simplexul pentru orice subset de puncte din M ​​3 , inclusiv triunghiul M 3 însuși . Dacă înglobăm M 3 ca triunghi regulat în planul euclidian , atunci complexul Cech de bile cu raza 1/2 centrate în punctele lui M 3 va conține toate celelalte simplexe ale complexului Vietoris-Rips, dar nu va conține un triunghi, deoarece nu există niciun punct în plan care să aparțină tuturor celor trei bile. Totuși, dacă M 3 este în schimb înglobat într-un spațiu metric care conține un al patrulea punct la o distanță de 1/2 de fiecare punct al lui M 3 , complexul Cech pentru bile cu raza 1/2 din acest spațiu va conține un triunghi. Astfel, complexul Cech pentru o rază fixă ​​de bile cu centre M3 depinde de spațiul în care poate fi încorporat M3 , în timp ce complexul Vietoris-Rips rămâne neschimbat .

Dacă un spațiu metric X este încorporat într-un spațiu metric injectiv Y , complexul Vietoris-Rips pentru distanță și mulțime X coincide cu complexul Cech de bile de rază centrate pe X în Y . Astfel, complexul Vietoris-Rips al oricărui spațiu metric M este egal cu complexul Cech al unui sistem de bile din carcasa injectivă a spațiului M .

Legătura cu graficele cercului unitar și complexele clicurilor

Complexul Vietoris-Rips pentru conține o margine pentru orice pereche de puncte care se află la sau mai puțin decât unitatea de distanță într-un spațiu metric dat. Și apoi scheletul său 1 este graficul cercurilor unitare ale punctelor sale. Conține un simplex pentru orice clică din graficul cerc unitar, deci este complexul steag (sau complexul clică) al graficului cerc unitar [6] . Mai general, complexul clică al oricărui graf G este complexul Vietoris-Rips pentru un spațiu metric având vârfurile lui G ca puncte și lungimile celor mai scurte căi din G ca distanță.

Alte rezultate

Dacă M este o varietate riemanniană închisă , atunci pentru valori suficient de mici, complexul Vietoris-Rips pentru M sau spații suficient de apropiate de M sunt homotopie echivalente cu M însuși [3] [7] .

Chambers, Erickson și Vora [6] au descris algoritmi eficienți pentru a determina dacă un anumit ciclu este contractibil în complexul Rips al oricărei mulțimi finite în planul euclidian .

Aplicații

Ca și în cazul graficelor de disc unitare, complexul Vietoris-Rips este utilizat în informatică pentru a modela topologia rețelelor ad-hoc fără fir . Unul dintre avantajele complexului Vietoris-Rips din această aplicație este că poate fi setat doar pe baza distanțelor dintre nodurile care interacționează, fără a fi nevoie să cunoască locația fizică a acestora. Dezavantajul este că, spre deosebire de complexul Cech, complexul Vietoris-Rips nu oferă în mod direct informații despre găurile din acoperirea comunicațiilor, dar acest dezavantaj poate fi redus prin plasarea complexului Cech între două complexe Vietoris-Rips pentru valori diferite [ 8] [9] . Implementarea complexelor Vietoris-Rips poate fi găsită în pachetul R TDAstats [10] .

Complexele Vietoris-Rips sunt, de asemenea, folosite pentru a evidenția caracteristicile din imagini. În această aplicație, complexul este construit într-un spațiu metric de dimensiuni înalte, în care punctele reprezintă caracteristici de imagine de ordin scăzut [11] .

Note

  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 .

Literatură