A minimal contouring approach to the computation of the Reeb graph

Given a manifold surface {\cal M} and a continuous scalar function f:{\cal M}\rightarrow {\hbox{\rlap{I}\kern 2.0pt{\hbox{R}}}}, the Reeb graph of ({\cal M},f) is a widely used high-level descriptor of {\cal M} and its usefulness has been demonstrated for a variety of applications, which range from shape parameterization and abstraction to deformation and comparison. In this context, we propose a novel contouring algorithm for the construction of a discrete Reeb graph with a minimal number of nodes, which correspond to the critical points of f (i.e., minima, maxima, and saddle points) and its level sets passing through the saddle points. In this way, we do not need to sample, sweep, or increasingly sort the f-values. Since most of the computation uses only local information on the mesh connectivity, equipped with the f-values at the surface vertices, the proposed approach is insensitive to noise and requires a small-memory footprint and temporary data structures. Furthermore, we maintain the parametric nature of the Reeb graph with respect to the input scalar function and we efficiently extract the Reeb graph of time-varying maps. Indicating with n and s the number of vertices of {\cal M} and saddle points of f, the overall computational cost O(sn) is competitive with respect to the O(n\,\log \,n) cost of previous work. This cost becomes optimal if {\cal M} is highly sampled or s\le \log n, as it happens for Laplacian eigenfunctions, harmonic maps, and one-forms.