Reeb Graphs and Reeb Spaces

Morse 関数のような実数値関数 \(f:X\to \R \) からは, level set の同じ connected component に属する点を同一視することにより, Reeb graph という graph ができる。 これは, Reeb により [Ree46] で定義されたものであるが, 最近応用トポロジーでよく使われている。 Trygsland [Try] によると, computer graphics で一般的になったのは, Shinagawa, Kunii, Koregosien の仕事 [SKK91] に依るところが大きいようである。

値域を一般の位相空間にした連続写像 \(f:X\to Y\) への一般化として, Reeb space がある。 Basu と Cox と Percival [BCP22] によると, Burlet と de Rham [BR74] により, 可微分多様体の間の良い smooth map の場合に Stein factorization という名前で導入されたのが最初らしい。

Reeb space を応用トポロジーに使うために, Edelsbrunner ら [EHP08] が combinatorial manifold 上の multivariate piecewise linear map の場合の Reeb space を定義している。

Reeb space を構成する algorithm については, Patel が thesis [Pat10] で考えている。

TDA などへの応用のためには, 元のデータに少しの変化があっても, 得られた結果にあまり変化がないこと, つまり robust であることが望ましい。そのために, persistence diagram では bottleneck distance などの距離が用いられているが, Reeb graph の距離については, 何種類か提案されている。 Bauer と Munch と Wang [BMW15] がそれらについて調べている。 Carrière と Oudot [CO17] は, 局所的に bottleneck distance を使うとよいと言っている。 de Silva と Munch と Patel [SMP16] は, Reeb graph の category は, Reeb cosheaf と呼ばれるある種の cosheaf の category と同値であることを示し, それを用いて Reeb graph の interleaving distance を定義している。

Reeb graph の一般化 (変種) としては, Reeb space の他に, Singh と Mémoli と Carlsson [SMC07] による Mapper という構成もある。Munch と Wang の [MW16] の section 2 の最後に簡潔な説明がある。TDA で使われている。

• Mapper

References

[BCP22]

Saugata Basu, Nathanael Cox, and Sarah Percival. “On the Reeb spaces of definable maps”. In: Discrete Comput. Geom. 68.2 (2022), pp. 372–405. arXiv: 1804 . 00605. url: https://doi.org/10.1007/s00454-022-00400-0.

[BMW15]

Ulrich Bauer, Elizabeth Munch, and Yusu Wang. “Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs”. In: 31st International Symposium on Computational Geometry. Vol. 34. LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015, pp. 461–475. arXiv: 1412.6646.

[BR74]

Oscar Burlet and Georges de Rham. “Sur certaines applications génériques d’une variété close à \(3\) dimensions dans le plan”. In: Enseignement Math. (2) 20 (1974), pp. 275–292.

[CO17]

Mathieu Carrière and Steve Oudot. “Local equivalence and intrinsic metrics between Reeb graphs”. In: 33rd International Symposium on Computational Geometry. Vol. 77. LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, Art. No. 25, 15. arXiv: 1703.02901.

[EHP08]

Herbert Edelsbrunner, John Harer, and Amit K. Patel. “Reeb spaces of piecewise linear mappings”. In: Computational geometry (SCG’08). ACM, New York, 2008, pp. 242–250. url: https://doi.org/10.1145/1377676.1377720.

[MW16]

Elizabeth Munch and Bei Wang. “Convergence between categorical representations of Reeb space and mapper”. In: 32nd International Symposium on Computational Geometry. Vol. 51. LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, Art. No. 53, 16. arXiv: 1512.04108.

[Pat10]

Amit Patel. “Reeb Spaces and the Robustness of Preimages”. PhD thesis. Duke University, 2010. url: https://www.math.colostate.edu/~akp/files/dissertation.pdf.

[Ree46]

Georges Reeb. “Sur les points singuliers d’une forme de Pfaff complètement intégrable ou d’une fonction numérique”. In: C. R. Acad. Sci. Paris 222 (1946), pp. 847–849.

[SKK91]

Yoshihisa Shinagawa, Tosiyasu L. Kunii, and Yannick L. Kergosien. “Surface coding based on Morse theory”. In: IEEE Computer Graphics and Applications 11.5 (Sept. 1991), pp. 66–78.

[SMC07]

Gurjeet Singh, Facundo Mémoli, and Gunnar E Carlsson. “Topological methods for the analysis of high dimensional data sets and 3d object recognition.” In: SPBG. 2007, pp. 91–100.

[SMP16]

Vin de Silva, Elizabeth Munch, and Amit Patel. “Categorified Reeb graphs”. In: Discrete Comput. Geom. 55.4 (2016), pp. 854–906. arXiv: 1501.04147. url: https://doi.org/10.1007/s00454-016-9763-9.

[Try]

Paul Trygsland. Combinatorial models for topological Reeb spaces. arXiv: 2109.05474.