Reeb graph

Reeb graph of the height function on the torus.

A Reeb graph (named after Georges Reeb) is a mathematical object reflecting the evolution of the level sets of a real-valued function on a manifold.[1] Originally introduced as a tool in Morse theory,[2] Reeb graphs found a wide variety of applications in computational geometry and computer graphics, including computer aided geometric design, topology-based shape matching,[3] topological simplification and cleaning, surface segmentation and parametrization, and efficient computation of level sets. In a special case of a function on a flat space, the Reeb graph forms a polytree and is also called a contour tree.[4]

Formal definition

Given a topological space X and a continuous function f: X  R, define an equivalence relation ∼ on X where pq whenever p and q belong to the same connected component of a single level set f1(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 f1(c). The pattern in which the arcs, or edges, meet at the nodes/vertices reflects the change in topology of the level set f1(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 f1(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 X1 and a component of f1(c) splits into two.

References

  1. Harish Doraiswamy, Vijay Natarajan, Efficient algorithms for computing Reeb graphs, Computational Geometry 42 (2009) 606–616
  2. 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
  3. Tung, Tony; Schmitt, Francis (2005). "The Augmented Multiresolution Reeb Graph Approach for Content-Based Retrieval of 3D Shapes". International Journal of Shape Modeling (IJSM) 11 (1): 91–120.
  4. Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), "Computing contour trees in all dimensions", Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 918–926.
This article is issued from Wikipedia - version of the Friday, February 05, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.