Toward Optimality in Discrete Morse Theory
Lewiner, Thomas ; Lopes, Hélio ; Tavares, Geovan
Experiment. Math., Tome 12 (2003) no. 1, p. 271-286 / Harvested from Project Euclid
Morse theory is a fundamental tool for investigating the topology of smooth manifolds. This tool has been extended to discrete structures by Forman, which allows combinatorial analysis and direct computation. This theory relies on discrete gradient vector fields, whose critical elements describe the topology of the structure. The purpose of this work is to construct optimal discrete gradient vector fields, where optimality means having the minimum number of critical elements. The problem is equivalently stated in terms of maximal hyperforests of hypergraphs. Deduced from this theoretical result, a algorithm constructing almost optimal discrete gradient fields is provided. The optimal parts of the algorithm are proved, and the part of exponential complexity is replaced by heuristics. Although reaching optimality is MAX-SNP hard, the experiments on odd topological models are almost always optimal.
Publié le : 2003-05-14
Classification:  Morse theory,  Forman theory,  computational topology,  computational geometry,  solid modeling,  discrete mathematices,  58E05,  68U05,  57M15,  57M27,  57Q10
@article{1087329231,
     author = {Lewiner, Thomas and Lopes, H\'elio and Tavares, Geovan},
     title = {Toward Optimality in Discrete Morse Theory},
     journal = {Experiment. Math.},
     volume = {12},
     number = {1},
     year = {2003},
     pages = { 271-286},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1087329231}
}
Lewiner, Thomas; Lopes, Hélio; Tavares, Geovan. Toward Optimality in Discrete Morse Theory. Experiment. Math., Tome 12 (2003) no. 1, pp.  271-286. http://gdmltest.u-ga.fr/item/1087329231/