Random discrete Morse theory and a new library of triangulations
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Random discrete Morse theory and a new library of triangulations. / Benedetti, Bruno ; Lutz, Frank Hagen.
I: Experimental Mathematics, Bind 23, Nr. 1, 2014, s. 66-94.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Random discrete Morse theory and a new library of triangulations
AU - Benedetti, Bruno
AU - Lutz, Frank Hagen
PY - 2014
Y1 - 2014
N2 - We introduce random discrete Morse theory as a computational scheme to measure the complexity of a triangulation. The idea is to try to quantify the frequency of discrete Morse matchings with few critical cells. Our measure will depend on the topology of the space, but also on how nicely the space is triangulated. The scheme we propose looks for optimal discrete Morse functions with an elementary random heuristic. Despite its naiveté, this approach turns out to be very successful even in the case of huge inputs. In our view, the existing libraries of examples in computational topology are “too easy” for testing algorithms based on discrete Morse theory. We propose a new library containing more complicated (and thus more meaningful) test examples.
AB - We introduce random discrete Morse theory as a computational scheme to measure the complexity of a triangulation. The idea is to try to quantify the frequency of discrete Morse matchings with few critical cells. Our measure will depend on the topology of the space, but also on how nicely the space is triangulated. The scheme we propose looks for optimal discrete Morse functions with an elementary random heuristic. Despite its naiveté, this approach turns out to be very successful even in the case of huge inputs. In our view, the existing libraries of examples in computational topology are “too easy” for testing algorithms based on discrete Morse theory. We propose a new library containing more complicated (and thus more meaningful) test examples.
U2 - 10.1080/10586458.2013.865281
DO - 10.1080/10586458.2013.865281
M3 - Journal article
VL - 23
SP - 66
EP - 94
JO - Experimental Mathematics
JF - Experimental Mathematics
SN - 1058-6458
IS - 1
ER -
ID: 138512989