Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9654916 | Computational Geometry | 2005 | 16 Pages |
Abstract
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(logn) time per pseudo-triangulation.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sergey Bereg,