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 [Vej14] によると, Edelsbrunner ら [EKS83], [EM94] により導入された。

• \(\alpha \)-complex

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

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

他に目にしたものを挙げると以下のようになる。

• graph induced complex [DFW]
• DTM-filtration [Ana+20]
• chromatic alpha filtration, chromatic Delaunay-Čech filtration, chromatic Delaunay-Rips filtration [Nat+]

References

[Ana+20]

Hirokazu Anai et al. “DTM-based filtrations”. In: Topological data analysis—the Abel Symposium 2018. Vol. 15. Abel Symp. Springer, Cham, [2020] ©2020, pp. 33–66. isbn: 978-3-030-43407-6; 978-3-030-43408-3. arXiv: 1811.04757. url: https://doi.org/10.1007/978-3-030-43408-3_2.

[BE17]

Ulrich Bauer and Herbert Edelsbrunner. “The Morse theory of Čech and Delaunay complexes”. In: Trans. Amer. Math. Soc. 369.5 (2017), pp. 3741–3762. arXiv: 1312.1231. url: https://doi.org/10.1090/tran/6991.

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

[DFW]

Tamal K. Dey, Fengtao Fan, and Yusu Wang. Graph Induced Complex on Point Data. arXiv: 1304.0662.

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

[Nat+]

Abhinav Natarajan, Thomas Chaplin, Adam Brown, and Maria-Jose Jimenez. Morse theory for chromatic Delaunay triangulations. arXiv: 2405.19303.

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

[Vej14]

Mikael Vejdemo-Johansson. “Sketches of a platypus: a survey of persistent homology and its algebraic foundations”. In: Algebraic topology: applications and new directions. Vol. 620. Contemp. Math. Amer. Math. Soc., Providence, RI, 2014, pp. 295–319. arXiv: 1212.5398. url: https://doi.org/10.1090/conm/620/12371.