Counting and enumerating pointed pseudo-triangulations with the greedy flip algorithm

• Version accepted to SIAM Journal on Computing. (3.5MB) (226KB)
• Version to appear at ALENEX 2005. (3.7MB) (324KB)
• Code available: Pseudo-Triangulation Toolkit Homepage

Abstract: This paper studies (pointed, or minimal) 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 exactly three have angles less than π. In particular, there is a natural flip operation on every internal edge. We establish fundamental properties of pointed pseudo-triangulations. We also present an algorithm to enumerate the pseudo-triangulations of a given point set, based on the greedy flip of Pocchiola and Vegter. 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 $\#T\le \; \#PT$ for all sets of $n\le 10$ points.)

Related Publications:

• Designing and implementing a general purpose halfedge data structure: WAE 2001.