Next: Problem 41: Sorting X+Y (Pairwise Sums)
Previous: Problem 39: Distances among Point Sets in \R^2 and \R^3
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.
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
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. http://www.cs.unc.edu/Research/compgeom/pseudoT/, 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. http://www.cs.uleth.ca/~wismath/cccg/papers/open.pdf.
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.