Discrete Morse theory
Discrete Morse theory is a combinatorial adaptation of Morse theory developed by Robin Forman. The theory has various practical applications in diverse fields of applied mathematics and computer science, such as configuration spaces,[1] homology computation,[2][3] denoising,[4] mesh compression,[5] and topological data analysis.[6]
Notation regarding CW complexes
[edit]Let be a CW complex and denote by its set of cells. Define the incidence function in the following way: given two cells and in , let be the degree of the attaching map from the boundary of to . The boundary operator is the endomorphism of the free abelian group generated by defined by
It is a defining property of boundary operators that . In more axiomatic definitions[7] one can find the requirement that
which is a consequence of the above definition of the boundary operator and the requirement that .
Discrete Morse functions
[edit]A real-valued function is a discrete Morse function if it satisfies the following two properties:
- For any cell , the number of cells in the boundary of which satisfy is at most one.
- For any cell , the number of cells containing in their boundary which satisfy is at most one.
It can be shown[8] that the cardinalities in the two conditions cannot both be one simultaneously for a fixed cell , provided that is a regular CW complex. In this case, each cell can be paired with at most one exceptional cell : either a boundary cell with larger value, or a co-boundary cell with smaller value. The cells which have no pairs, i.e., whose function values are strictly higher than their boundary cells and strictly lower than their co-boundary cells are called critical cells. Thus, a discrete Morse function partitions the CW complex into three distinct cell collections: , where:
- denotes the critical cells which are unpaired,
- denotes cells which are paired with boundary cells, and
- denotes cells which are paired with co-boundary cells.
By construction, there is a bijection of sets between -dimensional cells in and the -dimensional cells in , which can be denoted by for each natural number . It is an additional technical requirement that for each , the degree of the attaching map from the boundary of to its paired cell is a unit in the underlying ring of . For instance, over the integers , the only allowed values are . This technical requirement is guaranteed, for instance, when one assumes that is a regular CW complex over .
The fundamental result of discrete Morse theory establishes that the CW complex is isomorphic on the level of homology to a new complex consisting of only the critical cells. The paired cells in and describe gradient paths between adjacent critical cells which can be used to obtain the boundary operator on . Some details of this construction are provided in the next section.
The Morse complex
[edit]A gradient path is a sequence of paired cells
satisfying and . The index of this gradient path is defined to be the integer
The division here makes sense because the incidence between paired cells must be . Note that by construction, the values of the discrete Morse function must decrease across . The path is said to connect two critical cells if . This relationship may be expressed as . The multiplicity of this connection is defined to be the integer . Finally, the Morse boundary operator on the critical cells is defined by
where the sum is taken over all gradient path connections from to .
Basic results
[edit]Many of the familiar results from continuous Morse theory apply in the discrete setting.
The Morse inequalities
[edit]Let be a Morse complex associated to the CW complex . The number of -cells in is called the -th Morse number. Let denote the -th Betti number of . Then, for any , the following inequalities[9] hold
- , and
Moreover, the Euler characteristic of satisfies
Discrete Morse homology and homotopy type
[edit]Let be a regular CW complex with boundary operator and a discrete Morse function . Let be the associated Morse complex with Morse boundary operator . Then, there is an isomorphism[10] of homology groups
and similarly for the homotopy groups.
Applications
[edit]Discrete Morse theory finds its application in molecular shape analysis,[11] skeletonization of digital images/volumes,[12] graph reconstruction from noisy data,[13] denoising noisy point clouds[14] and analysing lithic tools in archaeology.[15]
See also
[edit]- Digital Morse theory
- Stratified Morse theory
- Shape analysis
- Topological combinatorics
- Discrete differential geometry
References
[edit]- ^ Mori, Francesca; Salvetti, Mario (2011), "(Discrete) Morse theory for Configuration spaces" (PDF), Mathematical Research Letters, 18 (1): 39–57, doi:10.4310/MRL.2011.v18.n1.a4, MR 2770581
- ^ Perseus: the Persistent Homology software.
- ^ Mischaikow, Konstantin; Nanda, Vidit (2013). "Morse Theory for Filtrations and Efficient computation of Persistent Homology". Discrete & Computational Geometry. 50 (2): 330–353. doi:10.1007/s00454-013-9529-6.
- ^ Bauer, Ulrich; Lange, Carsten; Wardetzky, Max (2012). "Optimal Topological Simplification of Discrete Functions on Surfaces". Discrete & Computational Geometry. 47 (2): 347–377. arXiv:1001.1269. doi:10.1007/s00454-011-9350-z.
- ^ Lewiner, T.; Lopes, H.; Tavares, G. (2004). "Applications of Forman's discrete Morse theory to topology visualization and mesh compression" (PDF). IEEE Transactions on Visualization and Computer Graphics. 10 (5): 499–508. doi:10.1109/TVCG.2004.18. PMID 15794132. S2CID 2185198. Archived from the original (PDF) on 2012-04-26.
- ^ "the Topology ToolKit". GitHub.io.
- ^ Mischaikow, Konstantin; Nanda, Vidit (2013). "Morse Theory for Filtrations and Efficient computation of Persistent Homology". Discrete & Computational Geometry. 50 (2): 330–353. doi:10.1007/s00454-013-9529-6.
- ^ Forman 1998, Lemma 2.5
- ^ Forman 1998, Corollaries 3.5 and 3.6
- ^ Forman 1998, Theorem 7.3
- ^ Cazals, F.; Chazal, F.; Lewiner, T. (2003). "Molecular shape analysis based upon the morse-smale complex and the connolly function". Proceedings of the nineteenth annual symposium on Computational geometry. ACM Press. pp. 351–360. doi:10.1145/777792.777845. ISBN 978-1-58113-663-0. S2CID 1570976.
- ^ Delgado-Friedrichs, Olaf; Robins, Vanessa; Sheppard, Adrian (March 2015). "Skeletonization and Partitioning of Digital Images Using Discrete Morse Theory". IEEE Transactions on Pattern Analysis and Machine Intelligence. 37 (3): 654–666. doi:10.1109/TPAMI.2014.2346172. hdl:1885/12873. ISSN 1939-3539. PMID 26353267. S2CID 7406197.
- ^ Dey, Tamal K.; Wang, Jiayuan; Wang, Yusu (2018). Speckmann, Bettina; Tóth, Csaba D. (eds.). Graph Reconstruction by Discrete Morse Theory. 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 99. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 31:1–31:15. doi:10.4230/LIPIcs.SoCG.2018.31. ISBN 978-3-95977-066-8. S2CID 3994099.
- ^ Mukherjee, Soham (2021-09-01). "Denoising with discrete Morse theory". The Visual Computer. 37 (9): 2883–94. doi:10.1007/s00371-021-02255-7. S2CID 237426675.
- ^ Bullenkamp, Jan Philipp; Linsel, Florian; Mara, Hubert (2022), "Lithic Feature Identification in 3D based on Discrete Morse Theory", Proceedings of Eurographics Workshop on Graphics and Cultural Heritage (GCH), Delft, Netherlands: Eurographics Association, pp. 55–58, doi:10.2312/VAST/VAST10/131-138, ISBN 9783038681786, ISSN 2312-6124, S2CID 17294591, retrieved 2022-10-05
- Forman, Robin (1998). "Morse theory for cell complexes" (PDF). Advances in Mathematics. 134 (1): 90–145. doi:10.1006/aima.1997.1650.
- Forman, Robin (2002). "A user's guide to discrete Morse theory" (PDF). Séminaire Lotharingien de Combinatoire. 48: Art. B48c, 35 pp. MR 1939695.
- Kozlov, Dmitry (2007). Combinatorial algebraic topology. Algorithms and Computation in Mathematics. Vol. 21. Springer. ISBN 978-3540719618. MR 2361455.
- Jonsson, Jakob (2007). Simplicial complexes of graphs. Springer. ISBN 978-3540758587.
- Orlik, Peter; Welker, Volkmar (2007). Algebraic Combinatorics: Lectures at a Summer School In Nordfjordeid. Universitext. Springer. doi:10.1007/978-3-540-68376-6. ISBN 978-3540683759. MR 2322081.
- "Discrete Morse theory". nLab.