Applications of Forman's discrete Morse theory to topology visualization and mesh compression.
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 work aims to build, visualize, and apply the basic elements of Forman's discrete Morse theory. It intends to use some of those 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.
Lewiner
Thomas
T
Laboratório MatMídia, Departamento de Matemática, Pontifícia Universidade Católica do Rio de Janeiro, Rua Marques de São Vicente 225, Gávea, Rio de Janeiro, RJ, Brasil. tomlew@mat.puc-rio.br
Lopes
Hélio
H
Tavares
Geovan
G
D000465:Algorithms; D001185:Artificial Intelligence; D003196:Computer Graphics; D017076:Computer-Aided Design; D044962:Data Compression / Q000379:methods*; D020342:Finite Element Analysis; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D021621:Imaging, Three-Dimensional / Q000379:methods*; D012815:Signal Processing, Computer-Assisted; D014584:User-Computer Interface