×

Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm. (English) Zbl 1120.68104

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

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W05 Nonnumerical algorithms
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

Citations:

Zbl 0857.68063
PDFBibTeX XMLCite
Full Text: DOI Link