Enumerating pseudo-triangulations in the plane
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.
scientific article; zbMATH DE number 2167822
scientific article