Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm

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 $\pi$. 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; \emph{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.