Premium
Morse complexes for shape segmentation and homological analysis: discrete models and algorithms
Author(s) -
De Floriani Leila,
Fugacci Ulderico,
Iuricich Federico,
Magillo Paola
Publication year - 2015
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.12596
Subject(s) - discrete morse theory , morse theory , morse code , circle valued morse theory , persistent homology , morse homology , computational topology , function (biology) , computer science , mathematics , algorithm , theoretical computer science , pure mathematics , algebra over a field , scalar field , cellular homology , telecommunications , evolutionary biology , mathematical physics , biology
Morse theory offers a natural and mathematically‐sound tool for shape analysis and understanding. It allows studying the behavior of a scalar function defined on a manifold. Starting from a Morse function, we can decompose the domain of the function into meaningful regions associated with the critical points of the function. Such decompositions, called Morse complexes, provide a segmentation of a shape and are extensively used in terrain modeling and in scientific visualization. Discrete Morse theory, a combinatorial counterpart of smooth Morse theory defined over cell complexes, provides an excellent basis for computing Morse complexes in a robust and efficient way. Moreover, since a discrete Morse complex computed over a given complex has the same homology as the original one, but fewer cells, discrete Morse theory is a fundamental tool for efficiently detecting holes in shapes through homology and persistent homology. In this survey, we review, classify and analyze algorithms for computing and simplifying Morse complexes in the context of such applications with an emphasis on discrete Morse theory and on algorithms based on it.