article

Optimal Topological Simplification of Discrete Functions on Surfaces

Authors:

Max WardetzkyAuthors Info & Claims

Discrete & Computational Geometry, Volume 47, Issue 2

Pages 347 - 377

Published: 01 March 2012 Publication History

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.

References

[1]

Agarwal, P.K., Arge, L., Yi, K.: I/O-efficient batched union-find and its applications to terrain analysis. In: SCG '06: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, pp. 167---176. ACM, New York (2006)

[2]

Attali, D., Glisse, M., Hornus, S., Lazarus, F., Morozov, D.: Persistence-sensitive simplification of functions on surfaces in linear time. Preprint (2008)

[3]

Banchoff, T.: Critical points and curvature for embedded polyhedra. J. Differ. Geom. 1(3---4), 245---256 (1967)

[4]

Bauer, U.: Persistence in discrete Morse theory. PhD thesis, University of Göttingen (2011)

[5]

Chari, M.K.: On discrete Morse functions and combinatorial decompositions. Discrete Math. 217(1---3), 101---113 (2000)

[6]

Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discrete Comput. Geom. 37(1), 103---120 (2007)

Digital Library

[7]

Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Extending persistence using Poincaré and Lefschetz duality. Found. Comput. Math. 9(1), 79---103 (2008)

[8]

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)

[9]

Danner, A., MØlhave, T., Yi, K., Agarwal, P.K., Arge, L., Mitasova, H.: Terra-Stream: from elevation data to watershed hierarchies. In: GIS '07: Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems, pp. 1---8. ACM, New York (2007)

Digital Library

[10]

de Silva, V., Morozov, D., Vejdemo-Johansson, M.: Dualities in persistent (co)homology. Unpublished manuscript (2010)

[11]

Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28(4), 511---533 (2002)

Digital Library

[12]

Edelsbrunner, H., Harer, J., Zomorodian, A.: Hierarchical Morse---Smale complexes for piecewise linear 2-manifolds. Discrete Comput. Geom. 30(1), 87---107 (2003)

[13]

Edelsbrunner, H., Morozov, D., Pascucci, V.: Persistence-sensitive simplification functions on 2-manifolds. In: SCG '06: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, pp. 127---134. ACM, New York (2006)

[14]

Eells, J., Kuiper, N.: Manifolds which are like projective planes. Publ. Math. Inst. Hautes Études Sci. 14(1), 5---46 (1962)

[15]

Forman, R.: Morse theory for cell complexes. Adv. Math. 134(1), 90---145 (1998)

[16]

Forman, R.: A user's guide to discrete Morse theory. Sémin. Lothar. Comb. B48c, 1---35 (2002)

[17]

Gray, C., Kammer, F., Löffler, M., Silveira, R.I.: Removing local extrema from imprecise terrains. Preprint (2010). arXiv:1002.2580

[18]

Gyulassy, A., Natarajan, V., Pascucci, V., Hamann, B.: Efficient computation of Morse---Smale complexes for three-dimensional scalar functions. IEEE Trans. Vis. Comput. Graph. 13(6), 1440---1447 (2007)

Digital Library

[19]

Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)

[20]

Jenson, S.K., Domingue, J.O.: Extracting topographic structure from digital elevation data for geographic information system analysis. Photogramm. Eng. Remote Sens. 54(11), 1593---1600 (1988)

[21]

Joswig, M., Pfetsch, M.E.: Computing optimal Morse matchings. SIAM J. Discrete Math. 20(1), 11---25 (2006)

Digital Library

[22]

Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology, 1st edn. Applied Mathematical Sciences, vol. 157. Springer, Berlin (2004)

[23]

King, H., Knudson, K., Mramor, N.: Generating discrete Morse functions from point data. Exp. Math. 14(4), 435---444 (2005)

[24]

Kosinski, A.: Singularities of piecewise linear mappings. I Mappings into the real line. Bull. Am. Math. Soc. 68(2), 110---114 (1962)

[25]

Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48---50 (1956)

[26]

Kühnel, W.: Triangulations of manifolds with few vertices. In: Tricerri, F. (ed.) Advances in Differential Geometry and Topology, pp. 59---114. World Scientific, Singapore (1990)

[27]

Large Geometric Models Archive. Georgia Institute of Technology. Available from: http://www.cc.gatech.edu/projects/large_models/

[28]

Lewiner, T., Lopes, H., Tavares, G.: Optimal discrete Morse functions for 2-manifolds. Comput. Geom. 26(3), 221---233 (2003)

Digital Library

[29]

Lundell, A.T., Weingram, S.: The Topology of CW Complexes. Van Nostrand-Reinhold, New York (1969)

[30]

Milnor, J.: Morse Theory. Annals of Mathematics Studies, vol. 51. Princeton University Press, Princeton (1963)

[31]

Morozov, D.: Homological illusions of persistence and stability. PhD thesis, Duke University (2008)

[32]

Morse, M.: The elimination of critical points of a non-degenerate function on a differentiable manifold. J. Anal. Math. 13(1), 257---316 (1964)

[33]

Soille, P.: Morphological carving. Pattern Recognit. Lett. 25(5), 543---550 (2004)

Digital Library

[34]

Soille, P.: Optimal removal of spurious pits in grid digital elevation models. Water Resour. Res. 40(12), W12509+ (2004)

[35]

Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25---57 (2006)

Digital Library

[36]

Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete Comput. Geom. 33(2), 249---274 (2005)

Digital Library

Cited By

Wang SWang WZhao H(2023)Using Foliation Leaves to Extract Reeb Graphs on SurfacesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.314176429:4(2117-2131)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TVCG.2022.3141764
Nigmetov AMorozov DTaufer MBalaji PPeña A(2019)Local-global merge tree computation with local exchangesProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3295500.3356188(1-13)Online publication date: 17-Nov-2019
https://dl.acm.org/doi/10.1145/3295500.3356188
Dey TWang JWang Y(2017)Improved Road Network Reconstruction using Discrete Morse TheoryProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3140031(1-4)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3140031
Show More Cited By

Optimal Topological Simplification of Discrete Functions on Surfaces
1. Theory of computation

Recommendations

Discrete Morse Theory for Computing Zigzag Persistence
Abstract
We introduce a theoretical and computational framework to use discrete Morse theory as an efficient preprocessing in order to compute zigzag persistent homology. From a zigzag filtration of complexes $(X_{i})$ , we introduce a zigzag Morse filtration ... $_{}$ $_{}$
Complexes of discrete Morse functions

We investigate properties of the set of discrete Morse functions on a fixed simplicial complex as defined by Forman [5]. It is not difficult to see that the pairings of discrete Morse functions of @D again form a simplicial complex, the complex of ...
Computing discrete Morse complexes from simplicial complexes
Graphical abstract

Display Omitted

Abstract
We consider the problem of efficiently computing a discrete Morse complex on simplicial complexes of arbitrary dimension and very large size. Based on a common graph-based formalism, we analyze existing data structures for simplicial ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete & Computational Geometry

Discrete & Computational Geometry Volume 47, Issue 2

March 2012

219 pages

ISSN:0179-5376

Issue’s Table of Contents

Copyright © Copyright © 2012 Springer Science+Business Media, LLC.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 March 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang SWang WZhao H(2023)Using Foliation Leaves to Extract Reeb Graphs on SurfacesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.314176429:4(2117-2131)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TVCG.2022.3141764
Nigmetov AMorozov DTaufer MBalaji PPeña A(2019)Local-global merge tree computation with local exchangesProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3295500.3356188(1-13)Online publication date: 17-Nov-2019
https://dl.acm.org/doi/10.1145/3295500.3356188
Dey TWang JWang Y(2017)Improved Road Network Reconstruction using Discrete Morse TheoryProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3140031(1-4)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3140031
Rathod ABin Masood TNatarajan V(2017)Approximation algorithms for Max Morse MatchingComputational Geometry: Theory and Applications10.1016/j.comgeo.2016.10.00261:C(1-23)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.comgeo.2016.10.002
Patan G(2017)Mesh-based and meshless design and approximation of scalar functionsComputer Aided Geometric Design10.1016/j.cagd.2017.05.00557:C(23-43)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1016/j.cagd.2017.05.005
Plonka GZheng Y(2016)Relation between total variation and persistence distance and its application in signal processingAdvances in Computational Mathematics10.1007/s10444-015-9438-842:3(651-674)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/s10444-015-9438-8
Reina-Molina RDíaz-Pernil DReal PBerciano A(2015)Membrane parallelism for discrete Morse theory applied to digital imagesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-014-0246-z26:1-2(49-71)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s00200-014-0246-z
Morozov DWeber G(2013)Distributed merge treesACM SIGPLAN Notices10.1145/2517327.244252648:8(93-102)Online publication date: 23-Feb-2013
https://dl.acm.org/doi/10.1145/2517327.2442526
Attali DBauer UDevillers OGlisse MLieutier Ada Fonseca GLewiner TPeñaranda LChan TKlein R(2013)Homological reconstruction and simplification in R3Proceedings of the twenty-ninth annual symposium on Computational geometry10.1145/2462356.2462373(117-126)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2462356.2462373
Morozov DWeber GNicolau AShen XAmarasinghe SVuduc R(2013)Distributed merge treesProceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/2442516.2442526(93-102)Online publication date: 23-Feb-2013
https://dl.acm.org/doi/10.1145/2442516.2442526
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents