Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, Jack Scott Snoeyink · SIAM Journal on Computing · 2006
We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Discrete Comput. Geom. 16 (1996), pp. 419–453]. Our two independent implementations agree and allow us to experimentally verify or disprove conjectures on the numbers of pointed pseudotriangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by the number of pointed pseudotriangulations for all sets of up to 10 points.)