Back to Search
Start Over
COUNTING AND ENUMERATING POINTED PSEUDOTRIANGULATIONS WITH THE GREEDY FLIP ALGORITHM.
- Source :
- SIAM Journal on Computing; 2006, Vol. 36 Issue 3, p721-739, 19p, 2 Illustrations, 6 Diagrams, 3 Charts
- Publication Year :
- 2006
-
Abstract
- We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Discrete Comput. Geom. 16 (1996), pp. 419-453]. Our two independent implementations agree and allow us to experimentally verify or disprove conjectures on the numbers of pointed pseudotriangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by the number of pointed pseudotriangulations for all sets of up to 10 points.) [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 36
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 24818173
- Full Text :
- https://doi.org/10.1137/050631008