Optimal topological simplification of discrete functions on surfaces

DOI10.1007/S00454-011-9350-ZzbMATH Open1243.57017arXiv1001.1269OpenAlexW3106485825MaRDI QIDQ664359FDOQ664359

Authors: Ulrich Bauer, M. Wardetzky, Carsten E. M. C. Lange 

Publication date: 1 March 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We solve the problem of minimizing the number of critical points among all functions on a surface within a prescribed distance {delta} from a given input function. The result is achieved by establishing a connection between discrete Morse theory and persistent homology. Our method completely removes homological noise with persistence less than 2{delta}, constructively proving the tightness of a lower bound on the number of critical points given by the stability theorem of persistent homology in dimension two for any input function. We also show that an optimal solution can be computed in linear time after persistence pairs have been computed.

Full work available at URL: https://arxiv.org/abs/1001.1269

Recommendations

• Optimal general simplification of scalar fields on surfaces
• Persistence in discrete Morse theory
• Topological persistence and simplification
• Generating Discrete Morse Functions from Point Data
• Toward Optimality in Discrete Morse Theory

zbMATH Keywords

Discrete Morse theoryCritical pointsPersistent homologyTopological denoising

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99) Critical points and critical submanifolds in differential topology (57R70) Abstract critical point theory (Morse theory, Lyusternik-Shnirel'man theory, etc.) in infinite-dimensional spaces (58E05) Real-valued functions in general topology (54C30) PL-topology (57Q99) Operations and obstructions in algebraic topology (55S99)

Cites Work

• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Title not available (Why is that?)
• Stability of persistence diagrams
• Introduction to algorithms.
• Morse theory for cell complexes
• Computing persistent homology
• Topological persistence and simplification
• Dualities in persistent (co)homology
• Morse Theory. (AM-51)
• Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds
• Computational homology
• Extending persistence using Poincaré and Lefschetz duality
• Critical points and curvature for embedded polyhedra
• Title not available (Why is that?)
• On discrete Morse functions and combinatorial decompositions
• Generating Discrete Morse Functions from Point Data
• A user's guide to discrete Morse theory
• Computing Optimal Morse Matchings
• Removing local extrema from imprecise terrains
• Optimal discrete Morse functions for 2-manifolds
• Manifolds which are like projective planes
• Title not available (Why is that?)
• The elimination of critical points of a non-degenerate function on a differentiable manifold
• Persistence in discrete Morse theory
• Title not available (Why is that?)
• Singularities of piecewise linear mappings. I Mappings into the real line

Cited In (14)

• Local, smooth, and consistent Jacobi set simplification
• Membrane parallelism for discrete Morse theory applied to digital images
• Persistence in discrete Morse theory
• Generating Discrete Morse Functions from Point Data
• A topological classification of convex bodies
• Relation between total variation and persistence distance and its application in signal processing
• Approximation algorithms for Max Morse matching
• An algorithmic discrete gradient field and the cohomology algebra of configuration spaces of two points on complete graphs
• Mesh-based and meshless design and approximation of scalar functions
• Optimal general simplification of scalar fields on surfaces
• Clear and compress: computing persistent homology in chunks
• Stability of critical points with interval persistence
• Graph reconstruction by discrete Morse theory
• Persistence barcodes versus Kolmogorov signatures: detecting modes of one-dimensional signals

Uses Software

• Ipopt

This page was built for publication: Optimal topological simplification of discrete functions on surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q664359)