Enumerating pseudo-triangulations

Pseudo-Triangulation. Pseudo-triangle is a simple polygon with exactly three convex vertices. Pseudo-triangulation of n points is a partition of their convex hull into interior disjoint pseudo-triangles whose vertices are given points. Minimum pseudo-triangulation of S is a pseudo-triangulation with the least number of edges among all pseudo-triangulations of S.

The basic operation on pseudo-triangulations is a flip.
Graph of pseudo-triangulations. We study the graph G whose vertices represent the pointed (or minimum) pseudo-triangulations of given points and whose edges represent flips. The graph G is connected. We construct a spanning tree of G, see Figure for an example. Based on the spanning tree we show that the pseudo-triangulations can be enumerated in O(logn) time per pseudo-triangulation.

pdf file submitted to a journal.


@article{b-eptp-05,
author = {Sergey Bereg},
title = {Enumerating Pseudo-Triangulations in the Plane},
journal = {Comput. Geom. Theory Appl.},
year = {2005},
volume = {30},
number = {3},
pages = {207--222},
url = {http://dx.doi.org/10.1016/j.comgeo.2004.09.002}
}