Optimal Topological Simplification of Discrete Functions on Surfaces

Abstract

Given a function f on a surface and a tolerance δ > 0, we construct a function fδ subject to ‖fδ - f‖∞ ≤ δ such that fδ has a minimum number of critical points. Our construction relies on a connection between discrete Morse theory and persistent homology and completely removes homological noise with persistence ≤ 2δ from the input function f. The number of critical points of the resulting simplified function fδ achieves the lower bound dictated by the stability theorem of persistent homology. We show that the simplified function can be computed in linear time after persistence pairs have been computed.