Affordable Access

Publisher Website

Efficient algorithms for computing Reeb graphs

Authors
Journal
Computational Geometry
0925-7721
Publisher
Elsevier
Publication Date
Volume
42
Identifiers
DOI: 10.1016/j.comgeo.2008.12.003
Keywords
  • Computational Topology
  • Algorithms
  • Dynamic Graph
  • Level Set
  • Manifold
  • Piecewise-Linear Function
  • Reeb Graph
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O ( n log n + n log g ( log log g ) 3 ) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O ( n log n ( log log n ) 3 ) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O ( n 2 ) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

There are no comments yet on this publication. Be the first to share your thoughts.