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