English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm

MPS-Authors
/persons/resource/persons44766

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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