next up previous
Next: Problem 41: Sorting X Up: The Open Problems Project Previous: Problem 39: Distances among

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+01,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: ≤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., 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.

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.

next up previous
Next: Problem 41: Sorting X Up: The Open Problems Project Previous: Problem 39: Distances among
The Open Problems Project - December 04, 2015