English

User Manual Privacy Policy Disclaimer Contact us

# 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.)