Constructing discrete Morse functions
Thomas Lewiner
Master Thesis (july 2002)
(also available in Portuguese, and in a short version presented at the Sibgrapi 2003 WTD)
(also available in Portuguese, and in a short version presented at the Sibgrapi 2003 WTD)
Abstract:
This work aims to study optimality in discrete Morse functions on general cell complex, where optimality entails having the least number of critical elements. This problem is proven here to be MAX-SNP hard. However, we provide a linear algorithm that, for the case of 2-manifolds, always reaches optimality. We prove here various results on the structure of a discrete Morse function. In particular, we provide an equivalent representation by hyperforests. From this point of view, we designed a construction of discrete Morse functions for general cell complexes of arbitrary finite dimension. The resulting algorithm is quadratic in time and, although not guaranteed to be optimal, gives optimal answers in most of the practical cases.Downloads:
PDF paper (2.9 MB)PPT presentation (5.9 MB)
BibTeX:
@mastersthesis{tomlew_msc,author = {Thomas Lewiner},
title = {Constructing discrete Morse functions},
year = {2002},
month = {july},
school = {Department of Mathematics, PUC-Rio},
url = {\url{http://thomas.lewiner.org/pdfs/tomlew_msc.pdf}}
}