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