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

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

Origin

[RRSS01].

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.

Bibliography

[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+03]

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.

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