Filtered Simplicial Complexes

Persistent homology では, point cloud data などから filtered simplicial complex を作り, その homology を取ることにより, poset \(\{1<2<\cdots <n\}\) の表現を作る。 その filtered simplicial complex の作り方には様々なものがある。

数学者に最もよく知られているのは Čech complex だろう。ここでいう Čech complex は, point cloud の各点の \(\varepsilon \) 近傍による covering に関する Čech complex のことである。

• Čech complex

ただ, Čech complex には, 点の数が増えると計算量が指数関数的に増えるという欠点がある。Botnan と Spreemann [BS] は, それを解決する ために, Čech complexを近似することを考えている。

もっとよく用いられる方法は, 別の種類の filtered simplicial complex を用いることである。 Persistent homology の計算で最も良く使われているのが, Vietoris-Rips complex である。

• Vietoris-Rips complex

Euclid 空間内に有限個の点があると, それによる Voronoi decomposition が得られるが, その covering の nerve として Delaunay complex が得られる。 Carlsson の [Car09] によると, witness complex は, それを \(\varepsilon \) 分だけ余裕を持たせたものである。Carlsson と de Silva [SC04] により導入された。

• strong witness complex
• weak witness complex

同じく Delaunay complex に関係したものとして, 他にも \(\alpha \)-complex というものがある。Vjedemo-Johansson [Vej] によると, Edelsbrunner ら [EKS83], [EM94] により導入された。

• \(\alpha \)-complex

Bauer と Edelsbrunner の [BE] には Delaunay complex とも呼ばれると書いてある。彼等は, 他に Delaunay-Čech complex や wrap complex という filtered simplicial complex を比較している。

• Delaunay-Čech complex [CK]
• wrap complex [Ede03]

References

[BE]

Ulrich Bauer and Herbert Edelsbrunner. The Morse theory of Čech and Delaunay complexes. arXiv: 1312.1231.

[BS]

Magnus Bakke Botnan and Gard Spreemann. Approximating Persistent Homology in Euclidean Space Through Collapses. arXiv: 1403.0533.

[Car09]

Gunnar Carlsson. “Topology and data”. In: Bull. Amer. Math. Soc. (N.S.) 46.2 (2009), pp. 255–308. url: http://dx.doi.org/10.1090/S0273-0979-09-01249-X.

[CK]

Harish Chintakunta and Hamid Krim. Distributed boundary tracking using alpha and Delaunay-Cech shapes. arXiv: 1302.3982.

[Ede03]

Herbert Edelsbrunner. “Surface reconstruction by wrapping finite sets in space”. In: Discrete and computational geometry. Vol. 25. Algorithms Combin. Berlin: Springer, 2003, pp. 379–404. url: http://dx.doi.org/10.1007/978-3-642-55566-4_17.

[EKS83]

Herbert Edelsbrunner, David G. Kirkpatrick, and Raimund Seidel. “On the shape of a set of points in the plane”. In: IEEE Trans. Inform. Theory 29.4 (1983), pp. 551–559. url: https://doi.org/10.1109/TIT.1983.1056714.

[EM94]

Herbert Edelsbrunner and Ernst P. Mücke. “Three-dimensional alpha shapes”. In: ACM Trans. Graph. 13.1 (Jan. 1994), pp. 43–72. url: http://doi.acm.org/10.1145/174462.156635.

[SC04]

Vin de Silva and Gunnar Carlsson. Topological estimation using witness complexes. Eurographics Symposium on Point-Based Graphics. 2004. eprint: \url{http://comptop.stanford.edu/u/preprints/witness.pdf}.

[Vej]

Mikael Vejdemo-Johansson. Sketches of a platypus: persistent homology and its algebraic foundations. arXiv: 1212.5398.