Enumerating pseudo-triangulations in the plane (Q1776895)

An algorithm for enumerating all pointed pseudo-triangulations of a set of \(n\) points in the plane is presented. It uses flips to generate pseudo-triangulations, it is based on a reverse search technique, and its running time is O\((\log n)\) per pseudo-triangulation. It can be used also to list the vertices of the polytope of pointed pseudo-triangulations. Moreover, it generates a spanning tree of the graph of pseudo-triangulations.