Reeb graph

客官°小女子只卖身不卖艺 2022-08-20 15:13 45阅读 0赞

From Wikipedia, the free encyclopedia

[![300px-3D-Leveltorus-Reebgraph.png][]][300px-3D-Leveltorus-Reebgraph.png 1]

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\]][1] Originally introduced as a tool in[Morse theory][],[\[2\]][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\]][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\]][4]

## Formal definition\[[edit][]\] ##

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*−1(*c*) for some real *c*. The **Reeb graph** is the [quotient space][] *X* /∼ endowed with the quotient topology.

## Description for Morse functions\[[edit][edit 1]\] ##

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*−1(*c*). The pattern in which the arcs, or edges, meet at the nodes/vertices reflects the change in topology of the level set *f*−1(*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*−1(*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*−1(*c*) splits into two.

## References\[[edit][edit 2]\] ##

1.  **[Jump up^][Jump up]** Harish Doraiswamy, Vijay Natarajan, [Efficient algorithms for computing Reeb graphs][], Computational Geometry 42 (2009) 606–616
2.  **[Jump up^][Jump up 1]** 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.  **[Jump up^][Jump up 2]** Tung, Tony; Schmitt, Francis (2005). ["The Augmented Multiresolution Reeb Graph Approach for Content-Based Retrieval of 3D Shapes"][The Augmented Multiresolution Reeb Graph Approach for Content-Based Retrieval of 3D Shapes]. *International Journal of Shape Modeling (IJSM)* **11** (1): 91–120.
4.  **[Jump up^][Jump up 3]** Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), "Computing contour trees in all dimensions", [*Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000)*][Proc. 11th ACM-SIAM Symposium on Discrete Algorithms _SODA 2000], pp. 918–926.

From Wikipedia, the free encyclopedia

[![300px-3D-Leveltorus-Reebgraph.png][]][300px-3D-Leveltorus-Reebgraph.png 1]

Reeb graph of the height function on the torus.

## Formal definition\[[edit][]\] ##

## Description for Morse functions\[[edit][edit 1]\] ##

## References\[[edit][edit 2]\] ##

[300px-3D-Leveltorus-Reebgraph.png]: https://upload.wikimedia.org/wikipedia/commons/thumb/4/47/3D-Leveltorus-Reebgraph.png/300px-3D-Leveltorus-Reebgraph.png
[300px-3D-Leveltorus-Reebgraph.png 1]: https://en.wikipedia.org/wiki/File:3D-Leveltorus-Reebgraph.png
[Georges Reeb]: https://en.wikipedia.org/wiki/Georges_Reeb
[mathematical]: https://en.wikipedia.org/wiki/Mathematics
[level sets]: https://en.wikipedia.org/wiki/Level_sets
[function]: https://en.wikipedia.org/wiki/Function_%28mathematics%29
[manifold]: https://en.wikipedia.org/wiki/Differentiable_manifold
[1]: https://en.wikipedia.org/wiki/Reeb_graph#cite_note-1
[Morse theory]: https://en.wikipedia.org/wiki/Morse_theory
[2]: https://en.wikipedia.org/wiki/Reeb_graph#cite_note-2
[computational geometry]: https://en.wikipedia.org/wiki/Computational_geometry
[computer graphics]: https://en.wikipedia.org/wiki/Computer_graphics
[computer aided geometric design]: https://en.wikipedia.org/wiki/Computer_aided_geometric_design
[topology]: https://en.wikipedia.org/wiki/Topology
[shape matching]: https://en.wikipedia.org/w/index.php?title=Shape_matching&action=edit&redlink=1
[3]: https://en.wikipedia.org/wiki/Reeb_graph#cite_note-3
[polytree]: https://en.wikipedia.org/wiki/Polytree
[4]: https://en.wikipedia.org/wiki/Reeb_graph#cite_note-4
[edit]: https://en.wikipedia.org/w/index.php?title=Reeb_graph&action=edit&section=1
[topological space]: https://en.wikipedia.org/wiki/Topological_space
[continuous function]: https://en.wikipedia.org/wiki/Continuous_function
[equivalence relation]: https://en.wikipedia.org/wiki/Equivalence_relation
[connected component]: https://en.wikipedia.org/wiki/Connected_component_%28topology%29
[level set]: https://en.wikipedia.org/wiki/Level_set
[quotient space]: https://en.wikipedia.org/wiki/Quotient_space_%28topology%29
[edit 1]: https://en.wikipedia.org/w/index.php?title=Reeb_graph&action=edit&section=2
[Morse function]: https://en.wikipedia.org/wiki/Morse_function
[critical values]: https://en.wikipedia.org/wiki/Critical_value
[degree]: https://en.wikipedia.org/wiki/Degree_%28graph_theory%29
[saddle point]: https://en.wikipedia.org/wiki/Saddle_point
[edit 2]: https://en.wikipedia.org/w/index.php?title=Reeb_graph&action=edit&section=3
[Jump up]: https://en.wikipedia.org/wiki/Reeb_graph#cite_ref-1
[Efficient algorithms for computing Reeb graphs]: http://www.sciencedirect.com/science/article/pii/S0925772108001193
[Jump up 1]: https://en.wikipedia.org/wiki/Reeb_graph#cite_ref-2
[Jump up 2]: https://en.wikipedia.org/wiki/Reeb_graph#cite_ref-3
[The Augmented Multiresolution Reeb Graph Approach for Content-Based Retrieval of 3D Shapes]: http://sites.google.com/site/tony2ng/home/amrg
[Jump up 3]: https://en.wikipedia.org/wiki/Reeb_graph#cite_ref-4
[Proc. 11th ACM-SIAM Symposium on Discrete Algorithms _SODA 2000]: http://portal.acm.org/citation.cfm?id=338659