Brönnimann, Hervé; Kettner, Lutz; Pocchiola, Michel; Snoeyink, Jack Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm. (English) Zbl 1120.68104 SIAM J. Comput. 36, No. 3, 721-739 (2006). Summary: We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of M. Pocchiola and G. Vegter [Discrete Comput. Geom. 16, 419–453 (1996; Zbl 0857.68063)]. 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.) Cited in 12 Documents MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 68W05 Nonnumerical algorithms 65D18 Numerical aspects of computer graphics, image analysis, and computational geometry Keywords:algorithm; pseudotriangulation; triangulation; combinatorics; enumeration Citations:Zbl 0857.68063 PDFBibTeX XMLCite \textit{H. Brönnimann} et al., SIAM J. Comput. 36, No. 3, 721--739 (2006; Zbl 1120.68104) Full Text: DOI Link