A minimal contouring approach to the computation of the Reeb graph

Area of Science:

• Computational geometry
• Computer graphics
• Applied mathematics

Background:

• Reeb graphs are crucial for analyzing manifold surfaces and scalar functions.
• Existing methods for Reeb graph construction can be computationally intensive and require extensive data sampling.

Purpose of the Study:

• To develop a novel, efficient algorithm for constructing discrete Reeb graphs.
• To minimize the number of nodes in the Reeb graph by focusing on critical points and saddle sets.
• To provide a noise-insensitive and memory-efficient approach for Reeb graph computation.

Main Methods:

• A novel contouring algorithm is proposed for discrete Reeb graph construction.
• The algorithm identifies critical points (minima, maxima, saddle points) and level sets through saddle points.
• Computation relies on local mesh connectivity and vertex f-values, avoiding sampling or sorting.

Main Results:

• The algorithm constructs discrete Reeb graphs with a minimal number of nodes.
• The computational cost is O(sn), which is competitive with O(n log n) methods.
• The approach is insensitive to noise and has a small memory footprint.
• Efficient extraction of Reeb graphs for time-varying maps is achieved.

Conclusions:

• The proposed algorithm offers an efficient and robust method for discrete Reeb graph construction.
• Its computational efficiency makes it suitable for large datasets and applications like shape analysis.
• The method maintains the parametric nature of Reeb graphs and handles time-varying data effectively.