de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/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. (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.)