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

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

- Statement
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+01], [O'R02a] for examples, explanation of the term “pointed,” and further details.

- Origin
- Status/Conjectures
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.

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

- Categories
triangulations; combinatorial geometry

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

- [AAKS02]
Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, and Bettina Speckmann. Convexity minimizes pseudo-triangulations. In

*Proc. 14th Canad. Conf. Comput. Geom.*, pages 158–161, 2002.- [BKPS01]
H. Brönnimann, L. Kettner, M. Pocchiola, and J. Snoeyink. Counting and enumerating pseudo-triangulations with the greedy flip algorithm. http://www.cs.unc.edu/Research/compgeom/pseudoT/, September 2001.

- [DO02]
Erik D. Demaine and Joseph O’Rourke. Open problems from CCCG 2001. In

*Proceedings of the 14th Canadian Conference on Computational Geometry*, August 2002. http://www.cs.uleth.ca/~wismath/cccg/papers/open.pdf.- [KKM+01]
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.*, 2001. To appear. Revision of abstract by L. Kettner, D. Kirkpatrick, and B. Speckmann, in*Proc. 13th Canad. Conf. Comput. Geom.*, pp. 117-120, 2001.- [O'R02a]
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.- [RRSS01]
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.- [Str00]
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.