Vietoris – Rips komplex - Vietoris–Rips complex

Komplex Vietoris – Rips ze sady 23 bodů v Euklidovské letadlo. Tento komplex má sady až čtyř bodů: samotné body (zobrazené jako červené kruhy), dvojice bodů (černé hrany), trojité body (bledě modré trojúhelníky) a čtyřnásobky bodů (tmavě modré čtyřstěny).

v topologie, Vietoris – Rips komplex, také nazývaný Vietoris komplex nebo Rips komplex, je abstraktní zjednodušený komplex které lze definovat z libovolného metrický prostor M a vzdálenost δ vytvořením a simplexní pro každého konečná množina bodů, které mají průměr nanejvýš δ. To znamená, že je to rodina konečných podmnožin M, ve kterém myslíme na podmnožinu k body jako tvořící (k - 1) -dimenzionální simplex (hrana pro dva body, trojúhelník pro tři body, čtyřstěn pro čtyři body atd.); pokud je konečná množina S má vlastnost, že vzdálenost mezi každou dvojicí bodů v S je nanejvýš δ, pak zahrneme S jako simplex v komplexu.

Dějiny

Komplex Vietoris – Rips byl původně nazýván komplexem Vietoris Leopold Vietoris, který jej zavedl jako prostředek k rozšíření teorie homologie od jednoduchých komplexů po metrické prostory.[1] Po Eliyahu Rips aplikoval stejný komplex na studium hyperbolické skupiny, jeho použití popularizovalo Michail Gromov  (1987 ), který jej nazval Ripsovým komplexem.[2] Název „Vietoris – Rips komplex“ je odvozen od Jean-Claude Hausmann  (1995 ).[3]

Vztah ke komplexu Čech

Komplex Vietoris – Rips úzce souvisí s Čechův komplex (nebo nerv ) sady koule, který má simplex pro každou konečnou podmnožinu koulí s neprázdným průnikem: v a geodeticky konvexní prostor Y, komplex Vietoris – Rips jakéhokoli podprostoru X ⊂ Y pro vzdálenost δ má stejné body a hrany jako Čechův komplex sady koulí o poloměru δ / 2 in Y které jsou vystředěny v bodech X. Na rozdíl od Čechova komplexu je však Vietoris – Ripsův komplex X záleží pouze na vnitřní geometrii X, a ne na jakékoli vložení X do nějakého většího prostoru.

Jako příklad zvažte jednotný metrický prostor M3 skládající se ze tří bodů, každý v jednotkové vzdálenosti od sebe. Komplex Vietoris – Rips M3, pro δ = 1, obsahuje simplex pro každou podmnožinu bodů v M3, včetně trojúhelníku pro M3 sám. Pokud vložíme M3 jako rovnostranný trojúhelník v Euklidovské letadlo, pak Čechův komplex koulí o poloměru 1/2 se středem v bodech M3 by obsahoval všechny ostatní simplexy komplexu Vietoris – Rips, ale neobsahoval by tento trojúhelník, protože ve všech třech koulích není žádný bod roviny. Pokud však M3 je místo toho vložen do metrického prostoru, který obsahuje čtvrtý bod ve vzdálenosti 1/2 od každého ze tří bodů M3, Čechův komplex koulí o poloměru 1/2 v tomto prostoru by obsahoval trojúhelník. Tedy Čechův komplex míčů s pevným poloměrem na střed M3 se liší v závislosti na tom, který větší prostor M3 může být vložen do, zatímco komplex Vietoris – Rips zůstává nezměněn.

Pokud existuje metrický prostor X je vložen do injektivní metrický prostor Y, komplex Vietoris – Rips pro vzdálenost δ a X se shoduje s Čechovým komplexem koulí o poloměru δ / 2 se středem v bodech X v Y. Tedy komplex Vietoris – Rips jakéhokoli metrického prostoru M se rovná Čechovu komplexu systému míčků v těsné rozpětí z M.

Vztah k jednotkovým diskovým grafům a klikovým komplexům

Komplex Vietoris – Rips pro δ = 1 obsahuje hranu pro každou dvojici bodů, které jsou v daném metrickém prostoru v jednotkové vzdálenosti nebo méně. Jako takový je jeho 1-kostra je graf jednotkového disku jeho bodů. Obsahuje simplex pro každého klika v grafu jednotkového disku, takže je to klikový komplex nebo komplex vlajky grafu jednotkového disku.[4] Obecněji řečeno, klikový komplex jakéhokoli grafu G je komplex Vietoris – Rips pro metrický prostor, který má body vrcholy z G a jako jeho vzdálenosti jsou délky nejkratší cesty v G.

Další výsledky

Li M je uzavřený Riemannovo potrubí, pak pro dostatečně malé hodnoty δ komplex Vietoris – Rips M, nebo prostorů dostatečně blízko k M, je ekvivalent homotopy na M sám.[5]

Chambers, Erickson & Worah (2008) popsat efektivní algoritmy pro určení, zda je daný cyklus kontrakční v Ripsově komplexu kteréhokoli konečného bodu nastaveného v Euklidovské letadlo.

Aplikace

Stejně jako u grafů jednotkových disků je i zde použit komplex Vietoris – Rips počítačová věda modelovat topologii bezdrátové komunikační sítě ad hoc. Jednou z výhod komplexu Vietoris – Rips v této aplikaci je, že jej lze určit pouze ze vzdáleností mezi komunikačními uzly, aniž by bylo nutné odvodit jejich přesné fyzické umístění. Nevýhodou je, že na rozdíl od komplexu Čech neposkytuje komplex Vietoris – Rips přímo informace o mezerách v pokrytí komunikace, ale tuto chybu lze napravit sendvičováním Čechova komplexu mezi dvěma komplexy Vietoris – Rips pro různé hodnoty δ.[6] Použitelnou implementaci komplexů Vietoris-Rips lze nalézt v TDAstats Balíček R.[7]

Komplexy Vietoris – Rips byly také použity pro extrakci prvků v digitálních obrazových datech; v této aplikaci je komplex postaven z vysoko-dimenzionálního metrického prostoru, ve kterém body představují prvky obrazu na nízké úrovni.[8]

Poznámky

  1. ^ Vietoris (1927); Lefschetz (1942); Hausmann (1995); Reitberger (2002).
  2. ^ Hausmann (1995); Reitberger (2002).
  3. ^ Reitberger (2002).
  4. ^ Chambers, Erickson & Worah (2008).
  5. ^ Hausmann (1995), Latschev (2001).
  6. ^ de Silva & Ghrist (2006), Muhammad & Jadbabaie (2007).
  7. ^ Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob (2018). „TDAstats: R pipeline for computing persistent homology in topological data analysis“. Journal of Open Source Software. 3 (28): 860. doi:10,21105 / joss.00860.
  8. ^ Carlsson, Carlsson & de Silva (2006).

Reference