Applications of Forman s discrete morse theory to topology visualization and mesh compression

Applications of Forman s discrete morse theory to topology visualization and mesh compression
Thomas Lewiner, Hélio Lopes, Geovan Tavares

Abstract:

Morse theory is a powerful tool for investigating the topology of smooth manifolds. It has been widely used by the computational topology, computer graphics and geometric modeling communities to devise topology based algorithms and data structures. Forman introduced a discrete version of this theory, which is purely combinatorial. This paper aims at building, visualizing and applying the basic elements of Forman s discrete Morse theory. It intends to use some of these concepts to visually study the topology of an object. As a basis, an algorithmic construction of optimal Forman s discrete gradient vector fields is provided. This construction is then used to topologically analyze mesh compression schemes, such as Edgebreaker and Grow&Fold. In particular, this paper proves that the complexity class of the strategy optimization of Grow&Fold is MAX-SNP hard.

Downloads:

PDF paper (1.2 MB)

BibTeX:

@article{morse_apps_tvcg,
    author = {Thomas Lewiner and Hélio Lopes and Geovan Tavares},
    title = {Applications of Forman s discrete morse theory to topology visualization and mesh compression},
    year = {2004},
    month = {september},
    journal = {Transactions on Visualization and Computer Graphics},
    volume = {10},
    number = {5},
    pages = {499--508},
    publisher = {IEEE},
    doi = {10.1109/TVCG.2004.18},
    url = {\url{http://thomas.lewiner.org/pdfs/morse_apps_tvcg.pdf}}
}