Optimal topological simplification of discrete functions on surfaces (Q664359)

In the study of functions given by measured data, the critical points which can be eliminated by small perturbations may be interpreted as being caused by noise. In order to remove this type of critical points, the general problem of topological simplification on surfaces is the following: given a function \(f\) on a surface \(X\) and a real number \(\delta >0\), find a function \(f_{\delta}\) which verifies \({\sup}_{x \in X}| f_{\delta}(x)-f(x)| \leq \delta\) and which minimizes the number of critical points. By using tools and results from discrete Morse theory and persistent homology, a solution is given in this paper for the class of discrete pseudo-Morse functions (which generalizes the class of discrete Morse functions and contains piecewise linear functions and pixel data) on combinatorial surfaces (or regular CW-complexes whose underlying space is a topological 2-manifold). Discrete vector fields and discrete Morse functions have been introduced by \textit{R. Forman} in [Adv. Math. 134, No. 1, 90--145 (1998; Zbl 0896.57023)]. A discrete vector field \(V\) on a regular CW-complex \(\mathcal{K}\) is a set of pairs of cells \((\sigma,\tau)\) where \(\sigma\) is a facet of \(\tau\) such that every cell of \(\mathcal{K}\) is contained in at most one pair of \(V\). A cell is critical with respect to \(V\) if it is not contained in any pair of \(V\). There is a natural notion of \(V\)-path associated to a discrete vector field \(V\) and a discrete vector field \(V\) without nontrivial closed \(V\)-paths is called a discrete gradient vector field. A function \(f :K \to \mathbb{R}\), defined on the set \(K\) of cells of \(\mathcal{K}\), is a discrete pseudo-Morse function if there is a discrete gradient vector field \(V\) on \(\mathcal{K}\) such that \[ (1)~~(\sigma,\tau)\not\in V \Longrightarrow f(\sigma)\leq f(\tau)\,\, \text{and}\,\, (2)~~(\sigma,\tau) \in V \Longrightarrow f(\sigma)\geq f(\tau) \] This definition extends the definition of discrete Morse functions (which are obtained by replacing the large inequality in (1) by a strict inequality) and these functions are used for introducing a symbolic perturbation scheme which permits to consider also degenerate functions (by using the fact that for a given discrete pseudo-Morse function \(f\) associated with a gradient vector field \(V\), one can find a discrete Morse function \(g\) associated with \(V\) and arbitrarily close to \(f\)). The authors present a second perturbation scheme in order to get a total order on the cells of the complex \(\mathcal{K}\). By this way, they apply the machinery of persistent homology (see the monography of [\textit{H. Edelsbrunner} and \textit{J. L. Harer}, Computational topology. Providence, RI: American Mathematical Society (AMS) (2010; Zbl 1193.55001)] or references given in the paper) to the filtration of the complex \(\mathcal{K}\) given by the order subcomplexes \(\mathcal{K}(\sigma)\), \(\sigma \in K\); in particular, they get persistence pairs \((\sigma,\tau)\) corresponding to homology classes \(h\) in \(H_*(\mathcal{K}(\sigma))\) which are born at \(\sigma\) and die entering \(\tau\). A persistence cancelation sequence is a sequence of discrete gradient vector fields \((V_0,V_1,\ldots,V_n)\) such that each \(V_i\) is constructed by removing (following a usual method introduced by Forman) a persistence pair \((\sigma_i,\tau_i)\) of critical points in \(V_{i-1}\). The central result of the paper is that for any discrete pseudo-Morse function \(f\) on a combinatorial surface \(\mathcal{K}\) and for any \(\delta \geq 0\), there is a discrete pseudo-Morse function \(f_{\delta}\) such that \({\sup}_{x \in \mathcal K}| f_{\delta}(x)-f(x)| \leq \delta\) and such that the number of persistence pairs of \(f_{\delta}\) is equal to the number of persistence pairs of \(f\) that have persistence \(>2\delta\) (the persistence of a persistence pair \((\sigma,\tau)\) of \(f\) is the number \(f(\tau)-f(\sigma)\)). This improves the Bottleneck Stability Theorem [\textit{D. Cohen-Steiner}, \textit{H. Edelsbrunner} and \textit{J. L. Harer}, Discrete Comput. Geom. 37, No. 1, 103--120 (2007; Zbl 1117.54027)] by proving that the lower bound on the number of critical points is optimal. The proof is contructive and leads to an algorithm that runs in time quadratic in the input size. The authors explain also how it is possible to get a more efficient algorithm (with linear time complexity).