Enumerating pseudotriangulations
PseudoTriangulation.
Pseudotriangle is a simple polygon with exactly three convex
vertices.
Pseudotriangulation of n points is a partition
of their convex hull into interior disjoint pseudotriangles whose
vertices are given points.
Minimum pseudotriangulation of S is a
pseudotriangulation with the least number of edges among all
pseudotriangulations of S.


The basic operation on pseudotriangulations is a flip.


Graph of pseudotriangulations.
We study the graph G whose vertices represent the
pointed (or minimum) pseudotriangulations 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 pseudotriangulations can
be enumerated in O(logn) time per
pseudotriangulation.


pdf file submitted to a journal.
@article{beptp05,
author = {Sergey Bereg},
title = {Enumerating PseudoTriangulations in the Plane},
journal = {Comput. Geom. Theory Appl.},
year = {2005},
volume = {30},
number = {3},
pages = {207222},
url = {http://dx.doi.org/10.1016/j.comgeo.2004.09.002}
}
