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.

Fig. 1. Pseudo-triangle.	Fig. 2. Minimum pseudo-triangulation of 11 points.

The basic operation on pseudo-triangulations is a flip.

Fig. 3. (a) Flip of traingles, (b) flip of pseudo-triangles.

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 Fig. 4 for an example. Based on the spanning tree we show that the pseudo-triangulations can be enumerated in O(logn) time per pseudo-triangulation.

Fig. 4. Tree of pseudo-triangulations.

Keywords: Pseudo-triangles; Pseudo-triangulations; Flips; Analysis of algorithms; Computational geometry; Triangulation of a polygon

@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}
}