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


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.

  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject
Last update: March 27, 2008.