Refereed Journal Paper

Counting and Enumerating Pointed Pseudo-Triangulations with the Greedy Flip Algorithm. Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, and Jack Snoeyink. In: SIAM Journal on Computing 36(3), pp. 721-739, 2006.

Abstract

This paper studies pseudo-triangulations for a given point set in the plane. Pseudo-triangulations have many properties of triangulations, and have more freedom since polygons with more than three vertices are allowed as long as they have exactly three inner angles less than . In particular, there is a natural flip operation on every internal edge. We present an algorithm to enumerate the pseudo-triangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Topologically sweeping visibility complexes via pseudo-triangulations; Discrete Comput. Geom. 16:419--453, 1996]. Our two independent implementations agree, and allow us to experimentally verify or disprove conjectures on the numbers of pseudo-triangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by than the number of pseudo-triangulations for all sets of up to 10 points.)

[PDF Preprint]
[Accompanying data and source code]