Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm
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.).
enumeration pseudotriangulation triangulation algorithm combinatorics