The Open Problems Project

Next: Problem 41: Sorting X+Y (Pairwise Sums)

Previous: Problem 39: Distances among Point Sets in \R^2 and \R^3

Problem 40: The Number of Pointed Pseudotriangulations


For a planar point set S, is the number of pointed pseudotriangulations always at least the number of triangulations?

A pseudotriangle is a planar polygon with exactly three convex vertices. Each pair of convex vertices is connected by a reflex chain, which may be just one segment. (Thus, a triangle is a pseudotriangle.) A pseudotriangulation of a set S of n points in the plane is a partition of the convex hull of S into pseudotriangles using S as a vertex set. A minimum pseudotriangulation, or pointed pseudotriangulation, has the fewest possible number of edges for a given set S of points.

See [Str00], [KKM+03], [O'R02a] for examples, explanation of the term “pointed,” and further details.




Open. Conjectured to be true, with equality only when the points of S are in convex position.

Partial and Related Results

The conjecture has been established for all sets of at most 10 points: \le 9 by [BKPS01], and 10 by Oswin Aichholzer [personal communication, 28 Mar. 2002]. Aichholzer et al. [AAKS02] establish that the number of pointed pseudotriangulations on n points is minimized when the points are in convex position.


Posed by Jack Snoeyink at the CCCG 2001 open-problem session [DO02].


triangulations; combinatorial geometry

Entry Revision History

J. O’Rourke, 20 Mar. 2002; 28 Mar. 2002; E. Demaine, 7 Aug. 2002; 31 Aug. 2002.



Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, and Bettina Speckmann. Convexity minimizes pseudo-triangulations. In Proc. 14th Canad. Conf. Comput. Geom., pages 158–161, 2002.


H. Brönnimann, L. Kettner, M. Pocchiola, and J. Snoeyink. Counting and enumerating pseudo-triangulations with the greedy flip algorithm., September 2001.


Erik D. Demaine and Joseph O’Rourke. Open problems from CCCG 2001. In Proceedings of the 14th Canadian Conference on Computational Geometry, August 2002.


Lutz Kettner, David Kirkpatrick, Andrea Mantler, Jack Snoeyink, Bettina Speckmann, and Fumihiko Takeuchi. Tight degree bounds for pseudo-triangulations of points. Comput. Geom. Th. Appl., 25(1–2), May 2003. Revision of abstract by L. Kettner, D. Kirkpatrick, and B. Speckmann, in Proc. 13th Canad. Conf. Comput. Geom., pp. 117-120, 2001.


J. O’Rourke. Computational geometry column 43. Internat. J. Comput. Geom. Appl., 12(3):263–265, 2002. Also in SIGACT News, 33(1) Issue 122, Mar. 2002, 58-60.


D. Randall, G. Rote, F. Santos, and J. Snoeyink. Counting triangulations and pseudotriangulations of wheels. In Proc. 13th Canad. Conf. Comput. Geom., pages 149–152, 2001.


Ileana Streinu. A combinatorial approach to planar non-colliding robot arm motion planning. In Proc. 41st Annu. IEEE Sympos. Found. Comput. Sci. IEEE, November 2000. 443–453.