# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### 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. (2005). Counting and
enumerating pointed pseudo-triangulations with the greedy flip algorithm. In *Proceedings of the Seventh
Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO
2005)* (pp. 98-110). Philadelphia, USA: SIAM.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-262A-F

##### 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 $\pi$. 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
the number of triangulations is less than the number of
pseudo-triangulations for all sets of less than 10 points; the proof
for all $n$ is still to be discovered.)