Harish Doraiswamy
Vijay Natarajan
ABSTRACT
The Reeb graph of a scalar function represents the evolution of the topology of its level sets. In this video, we describe a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Arcs in the Reeb graph are computed in the second step using a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The algorithm is also able to handle non-manifold domains.
- C. L. Bajaj, V. Pascucci, and D. R. Schikore. The contour spectrum. In Proc. IEEE Conf. Visualization, pages 167--173, 1997. Google Scholar
Digital Library
- T. F. Banchoff. Critical points and curvature for embedded polyhedral surfaces. Am. Math. Monthly, 77:475--485, 1970.Google ScholarCross Ref
- K. Cole-McLaughlin, H. Edelsbrunner, J. Harer, V. Natarajan, and V. Pascucci. Loops in Reeb graphs of 2-manifolds. Disc. Comput. Geom., 32(2):231--244, 2004. Google ScholarDigital Library
- H. Doraiswamy and V. Natarajan. Efficient output-sensitive construction of Reeb graphs. In Proc. Intl. Symp. Algorithms and Computation, pages 557--568, 2008. Google ScholarDigital Library
- H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001. Google ScholarDigital Library
- Y. Matsumoto. An Introduction to Morse Theory. Amer. Math. Soc., 2002. Translated from Japanese by K. Hudson and M. Saito.Google Scholar
- G. Reeb. Sur les points singuliers d'une forme de pfaff complètement intégrable ou d'une fonction numérique. Comptes Rendus de L'Académie ses Séances, Paris, 222:847--849, 1946.Google Scholar
- G. H. Weber, S. E. Dillard, H. Carr, V. Pascucci, and B. Hamann. Topology-controlled volume rendering. IEEE Trans. Vis. Comput. Graph., 13(2):330--341, 2007. Google ScholarDigital Library
Index Terms
- Constructing Reeb graphs using cylinder maps
Recommendations
Output-Sensitive Construction of Reeb Graphs
The Reeb graph of a scalar function represents the evolution of the topology of its level sets. This paper describes a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds or non-manifolds in ...
Computing Reeb Graphs as a Union of Contour Trees
The Reeb graph of a scalar function tracks the evolution of the topology of its level sets. This paper describes a fast algorithm to compute the Reeb graph of a piecewise-linear (PL) function defined over manifolds and non-manifolds. The key idea in the ...
Loops in reeb graphs of 2-manifolds
SCG '03: Proceedings of the nineteenth annual symposium on Computational geometryGiven a Morse function f over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower bounds on the number of loops in the Reeb graph that ...
Comments