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 [Streinu, 2000], [Kettner et al., 2003], [O'Rourke, 2002] for examples, explanation of the term \textquotedblleft{}pointed,\textquotedblright{} and further details.

Download

Abstract

Determine whether every planar point set has at least as many pointed pseudotriangulations as triangulations, with equality only in convex position.

Background and progress

The conjecture was investigated computationally and verified for point sets of up to ten points [Aichholzer et al., 2002]. Foundational enumeration work relates pointed pseudotriangulations to planar structures [Randall et al., 2001]; the general inequality remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p40.

Reference papers

Convexity minimizes pseudo-triangulationsOswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Bettina SpeckmannProceedings of the 14th Canadian Conference on Computational Geometry · 2002
Counting triangulations and pseudo-triangulations of wheelsDana Randall, Günter Rote, Francisco Santos, Jack SnoeyinkProceedings of the 13th Canadian Conference on Computational Geometry · 2001
A combinatorial approach to planar non-colliding robot arm motion planningIleana StreinuProc. 41st Annu. IEEE Sympos. Found. Comput. Sci. · 2000
Tight degree bounds for pseudo-triangulations of pointsLutz Kettner, David Kirkpatrick, Andrea Mantler, Jack Snoeyink, Bettina Speckmann, Fumihiko TakeuchiComput. Geom. Th. Appl. · 2003
Computational geometry column 43Joseph O'RourkeInternat. J. Comput. Geom. Appl. · 2002

The Number of Pointed Pseudotriangulations

Coming soon

Organizer