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