Vietoris-Rips complex

Rips complex あるいは Vietoris-Rips complex とは, Euclid空間, あるいはより一般に 距離空間の点の配置 (point cloud) から定義される, 単体的複体である。Chambers らの [Cha+10] や Hausmann の [Hau95] を見るのがよいと思う。それらによると, Vietoris により [Vie27] で距離空間の単体的複体のモデル, そして ホモロジーを定義するために導入されたらしい。 それが, Rips により hyperbolic group を調べるために使われるようになり, Gromov の [Gro87] などで Rips complex と呼ばれるようになったため, Rips complex という呼び方が定着したようである。

Gromov は, その論文の中で hyperbolic geodesic metric space に対し Vietoris-Rips complex が可縮になるための条件を述べているが, それは元々 Rips による結果のようである。Bauer と Roll [BR] がその一般化を考えている。

Hausmann は, [Hau95] でそのコホモロジーを半径を \(0\) に近づけた colimit として定義し, metric cohomology と呼んでいる。そのホモロジー版は, Vietoris により考えられていたようである。

最近では, de Silva と Ghrist の homological sensor network の研究 [SG07b; SG07a] の中で使われている。そして, topological data analysis で persistent homology の元になる simplicial complex としてよく使われる。

• persistent homology

画像データを topological data analysis の手法で解析するときの目的は, sampling した data から元の図形の持つ性質を取り出すことであるが, 計算機にかけるためには, 計算量が大きいと困る。Vietoris-Rips complex はその点で Čech complex より優れているようである。Vietoris-Rips complex から元の図形のホモトピー型が復元できることについては, Hausmann [Hau95] により, closed Riemannian manifold の場合に証明されている。Attali と Lieuter と Salinas は, 多様体ではない場合にどのような条件の下で元のホモトピー型を復元できるかを [ALS11] で調べている。 また Attali と Lieuterは, [AL15] では Vietoris-Rips complex を elementary collapse により「求める形」と同相な simplicial complex にできることを示している。

通常 persistent homology を使うときは, 計算機にかけるためもあり, ホモロジーが有限生成の場合のみを考えている。ところが, Chazal と Oudet [CSO14] や Droz [Dro] にあるように, ユークリッド空間のコンパクト集合で, その Vietoris-Rips complex のホモロジーが非可算無限の元で生成されているものもある。

Goff [Gof11] は Betti数の upper bound の評価を与えている。 その最後の section で quasi-Rips complex という変種についても考えている。 Quasi-Rips complex は, Chambers, de Silva, Erickson, Ghrist の [Cha+10] で導入されたもののようである。

• quasi-Rips complex

M. Kahle は, [Kah11; KM13] などで random Rips complex (や他の random simplicial complex) を調べている。

Engström は [Eng09] で不等号を逆にした anti-Rips complex を定義している。 グラフの independence complexと関係がある。

その chain complex に \(\ell ^1\)-norm を与えたものが, Bader と Furman と Sauer の [BFS13] で使われている。

Adamaszek, Adams, Frick [AAF18] は, simplicial complex ではなく metric space を作ることを考えている。元々が finite metric space なのだから, 距離の情報も失なわないようにしたい, ということのようである。円周の場合を調べたものとして, Moy の [Moy] がある。

• Vietoris-Rips thickening

References

[AAF18]

Michał Adamaszek, Henry Adams, and Florian Frick. “Metric reconstruction via optimal transport”. In: SIAM J. Appl. Algebra Geom. 2.4 (2018), pp. 597–619. arXiv: 1706.04876. url: https://doi.org/10.1137/17M1148025.

[AL15]

Dominique Attali and André Lieutier. “Geometry-driven collapses for converting a Čech complex into a triangulation of a nicely triangulable shape”. In: Discrete Comput. Geom. 54.4 (2015), pp. 798–825. arXiv: 1304.3680. url: https://doi.org/10.1007/s00454-015-9733-7.

[ALS11]

Dominique Attali, André Lieutier, and David Salinas. “Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes (extended abstract)”. In: Computational geometry (SCG’11). New York: ACM, 2011, pp. 491–500. url: http://dx.doi.org/10.1145/1998196.1998276.

[BFS13]

Uri Bader, Alex Furman, and Roman Sauer. “Efficient subdivision in hyperbolic groups and applications”. In: Groups Geom. Dyn. 7.2 (2013), pp. 263–292. arXiv: 1003.1562. url: https://doi.org/10.4171/GGD/182.

[BR]

Ulrich Bauer and Fabian Roll. Gromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations. arXiv: 2112.06781.

[Cha+10]

Erin W. Chambers, Vin de Silva, Jeff Erickson, and Robert Ghrist. “Vietoris-Rips complexes of planar point sets”. In: Discrete Comput. Geom. 44.1 (2010), pp. 75–90. arXiv: 0712.0395. url: https://doi.org/10.1007/s00454-009-9209-8.

[CSO14]

Frédéric Chazal, Vin de Silva, and Steve Oudot. “Persistence stability for geometric complexes”. In: Geom. Dedicata 173 (2014), pp. 193–214. arXiv: 1207.3885. url: https://doi.org/10.1007/s10711-013-9937-z.

[Dro]

Jean-Marie Droz. A subset of Euclidean space with large Vietoris-Rips homology. arXiv: 1210.4097.

[Eng09]

Alexander Engström. “Complexes of directed trees and independence complexes”. In: Discrete Math. 309.10 (2009), pp. 3299–3309. arXiv: math/0508148. url: http://dx.doi.org/10.1016/j.disc.2008.09.033.

[Gof11]

Michael Goff. “Extremal Betti numbers of Vietoris-Rips complexes”. In: Discrete Comput. Geom. 46.1 (2011), pp. 132–155. arXiv: 0910.0040. url: https://doi.org/10.1007/s00454-010-9274-z.

[Gro87]

M. Gromov. “Hyperbolic groups”. In: Essays in group theory. Vol. 8. Math. Sci. Res. Inst. Publ. New York: Springer, 1987, pp. 75–263.

[Hau95]

Jean-Claude Hausmann. “On the Vietoris-Rips complexes and a cohomology theory for metric spaces”. In: Prospects in topology (Princeton, NJ, 1994). Vol. 138. Ann. of Math. Stud. Princeton, NJ: Princeton Univ. Press, 1995, pp. 175–188.

[Kah11]

Matthew Kahle. “Random geometric complexes”. In: Discrete Comput. Geom. 45.3 (2011), pp. 553–573. arXiv: 0910.1649. url: https://doi.org/10.1007/s00454-010-9319-3.

[KM13]

Matthew Kahle and Elizabeth Meckes. “Limit theorems for Betti numbers of random simplicial complexes”. In: Homology Homotopy Appl. 15.1 (2013), pp. 343–374. arXiv: 1009.4130. url: https://doi.org/10.4310/HHA.2013.v15.n1.a17.

[Moy]

Michael Moy. Vietoris-Rips Metric Thickenings of the Circle. arXiv: 2206.03539.

[SG07a]

Vin de Silva and Robert Ghrist. “Coverage in sensor networks via persistent homology”. In: Algebr. Geom. Topol. 7 (2007), pp. 339–358. url: http://dx.doi.org/10.2140/agt.2007.7.339.

[SG07b]

Vin de Silva and Robert Ghrist. “Homological sensor networks”. In: Notices Amer. Math. Soc. 54.1 (2007), pp. 10–17.

[Vie27]

L. Vietoris. “Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen”. In: Math. Ann. 97.1 (1927), pp. 454–472. url: http://dx.doi.org/10.1007/BF01447877.