Günter Rote, Francisco Santos, and Ileana Streinu:
Pseudo-triangulations — a survey
In: Surveys on Discrete and Computational Geometry—Twenty Years Later.
Editors: Jacob E. Goodman, János Pach, and Richard Pollack. Contemporary
Mathematics, volume 453, American Mathematical Society, 2008, pp. 343–410.
arXiv:math/0612672 [math.CO].
Abstract
A pseudo-triangle is a simple polygon with three convex vertices, and a
pseudo-triangulation is a tiling of a planar region into pseudo-triangles.
Pseudo-triangulations appear as data structures in computational geometry,
as planar bar-and-joint frameworks in rigidity theory and as projections
of locally convex surfaces. This survey of current literature includes
combinatorial properties and counting of special classes, rigidity theoretical
results, representations as polytopes, straight-line drawings from abstract
versions called combinatorial pseudo-triangulations, algorithms and applications
of pseudo-triangulations.
Last update: March 27, 2008.