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. We aim to build, visualize, and apply the basic elements of Forman's discrete Morse theory. We intend 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, we prove that the complexity class of the strategy optimization of Grow&Fold is MAX-SNP hard.