“Reeb graph”的意思、由来-开放百科全书

A Reeb graph^[1] (named after Georges Reeb by René Thom) is a mathematical object reflecting the evolution of the level sets of a real-valued function on a manifold.^[2]

According to ^[3] a similar concept was introduced by G.M. Adelson-Velskii and A.S. Kronrod and applied to analysis of Hilbert's thirteenth problem.^[4] Proposed by G. Reeb as a tool in Morse theory,^[5] Reeb graphs found a wide variety of applications in computational geometry and computer graphics^[6]^[7], including computer aided geometric design, topology-based shape matching^[8],^[9],^[10] topological data analysis^[11], topological simplification and cleaning, surface segmentation and parametrization, efficient computation of level sets, and geometrical thermodynamics.^[3]

In a special case of a function on a flat space, the Reeb graph forms a polytree and is also called a contour tree.^[12]

Formal definition

Given a topological space X and a continuous function f: X → R, define an equivalence relation ∼ on X where p∼q whenever p and q belong to the same connected component of a single level set f⁻¹(c) for some real c. The Reeb graph is the quotient space X /∼ endowed with the quotient topology.

Description for Morse functions

If f is a Morse function with distinct critical values, the Reeb graph can be described more explicitly. Its nodes, or vertices, correspond to the critical level sets f⁻¹(c). The pattern in which the arcs, or edges, meet at the nodes/vertices reflects the change in topology of the level set f⁻¹(t) as t passes through the critical value c. For example, if c is a minimum or a maximum of f, a component is created or destroyed; consequently, an arc originates or terminates at the corresponding node, which has degree 1. If c is a saddle point of index 1 and two components of f⁻¹(t) merge at t = c as t increases, the corresponding vertex of the Reeb graph has degree 3 and looks like the letter "Y"; the same reasoning applies if the index of c is dim X−1 and a component of f⁻¹(c) splits into two.

References

1. ^ Y. Shinagawa, T.L. Kunii, and Y.L. Kergosien, 1991. Surface coding based on Morse theory. IEEE Computer Graphics and Applications, 11(5), pp.66-78
2. ^Harish Doraiswamy, Vijay Natarajan, Efficient algorithms for computing Reeb graphs, Computational Geometry 42 (2009) 606–616
3. ^¹A.N. Gorban, [https://www.researchgate.net/publication/235437324_Thermodynamic_Tree_The_Space_of_Admissible_Paths Thermodynamic Tree: The Space of Admissible Paths], SIAM Journal on Applied Dynamical Systems 12(1) (2013), 246-278.
4. ^G. M. Adelson-Velskii, A. S. Kronrod, About level sets of continuous functions with partial derivatives, Dokl. Akad. Nauk SSSR, 49 (4) (1945), pp. 239–241.
5. ^G. Reeb, Sur les points singuliers d’une forme de Pfaff complètement intégrable ou d’une fonction numérique, C. R. Acad. Sci. Paris 222 (1946) 847–849
6. ^ Y. Shinagawa, T.L. Kunii, and Y.L. Kergosien, 1991. Surface coding based on Morse theory. IEEE Computer Graphics and Applications, 11(5), pp.66-78
7. ^Y. Shinagawa and T.L. Kunii, 1991. Constructing a Reeb graph automatically from cross sections. IEEE Computer Graphics and Applications, 11(6), pp.44-51.
8. ^{{cite journal | last1 = Pascucci | first1 = Valerio | last2 = Scorzelli | first2 = Giorgio | last3 = Bremer | first3 = Peer-Timo | last4 = Mascarenhas | first4 = Ajith | title = Robust On-line Computation of Reeb Graphs: Simplicity and Speed | journal = ACM Transactions on Graphics (Proceedings of SIGGRAPH 2007) | volume = 26 | issue = 3 | pages = 58.1–58.9 | url = http://www.pascucci.org/pdf-papers/pascucci-siggraph-2007-Reeb-Graph.pdf | year = 2007| doi = 10.1145/1276377.1276449 }}
9. ^M. Hilaga, Y. Shinagawa, T. Kohmura and T.L. Kunii, 2001, August. Topology matching for fully automatic similarity estimation of 3D shapes. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques (pp. 203-212). ACM.
10. ^{{cite journal | last1 = Tung | first1 = Tony | last2 = Schmitt | first2 = Francis | title = The Augmented Multiresolution Reeb Graph Approach for Content-Based Retrieval of 3D Shapes | journal = International Journal of Shape Modeling (IJSM) | volume = 11 | issue = 1 | pages = 91–120 | url = http://sites.google.com/site/tony2ng/home/amrg | year = 2005| doi = 10.1142/S0218654305000748 }}
11. ^{{Cite web|url=https://topology-tool-kit.github.io/|title=the Topology ToolKit|last=|first=|date=|website=|archive-url=|archive-date=|dead-url=|access-date=}}
12. ^{{citation | last1 = Carr | first1 = Hamish | last2 = Snoeyink | first2 = Jack | last3 = Axen | first3 = Ulrike | contribution = Computing contour trees in all dimensions | pages = 918–926 | title = Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000) | url = http://portal.acm.org/citation.cfm?id=338659 | year = 2000}}.