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 としてよく使われる。
画像データを 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+] で導入されたもののようである。
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.
|