Vietoris-Rips complex

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

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は, [AL] では Vietoris-Rips complex を elementary collapse により「求める形」と同相な simplicial complex にできることを示している。

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

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

• quasi-Rips complex

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

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

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

References

[AL]

Dominique Attali and André Lieutier. Geometry-driven collapses for converting a Cech complex into a triangulation of a nicely triangulable shape. arXiv: 1304.3680.

[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.

[BFS]

Uri Bader, Alex Furman, and Roman Sauer. Efficient subdivision in hyperbolic groups and applications. arXiv: 1003.1562.

[Cha+]

Erin W. Chambers, Vin de Silva, Jeff Erickson, and Robert Ghrist. Rips Complexes of Planar Point Sets. arXiv: 0712.0395.

[CSO]

Frederic Chazal, Vin de Silva, and Steve Oudot. Persistence stability for geometric complexes. arXiv: 1207.3885.

[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.

[Gof]

Michael Goff. Extremal Betti numbers of Rips complexes. arXiv: 0910.0040.

[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.

[Kah]

Matthew Kahle. Random geometric complexes. arXiv: 0910.1649.

[KM]

Matthew Kahle and Elizabeth Meckes. Limit theorems for Betti numbers of random simplicial complexes. arXiv: 1009.4130.

[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.