hide
Free keywords:
-
Abstract:
This paper studies 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
they have exactly three inner angles less than $\pi$. In particular, there is a
natural flip operation on every internal edge. We present an algorithm to
enumerate the pseudo-triangulations of a given point set, based on the greedy
flip algorithm of Pocchiola and Vegter [Topologically sweeping visibility
complexes via pseudo-triangulations; \emph{Discrete Comput.\ Geom.}\ 16:419
453, 1996]. 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 bounded by than the number of
pseudo-triangulations for all sets of up to 10 points.)
