Enumerating pseudo-triangulations in the plane

摘要

A pseudo-triangle is a simple polygon with exactly three convex vertices. A pseudo-triangulation of a finite point set S in the plane is a partition of the convex hull of S into interior disjoint pseudo-triangles whose vertices are points of S. A pointed pseudo-triangulation is one which has the least number of pseudo-triangles. We study the graph G whose vertices represent the pointed pseudo-triangulations and whose edges represent flips. We present an algorithm for enumerating pointed pseudo-triangulations in O(log n) time per pseudo-triangulation. (c) 2004 Elsevier B.V. All rights reserved.