Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Journal Article

Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm


Kettner,  Lutz
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Brönnimann, H., Kettner, L., Pocchiola, M., & Snoeyink, J. (2006). Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm. SIAM Journal on Computing, 36(3), 721-739.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2488-B
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.)