The Number of Pointed Pseudotriangulations

For a planar point set $S$ in general position, let $p(S)$ be the number of pointed pseudotriangulations and $t(S)$ the number of triangulations. Prove or disprove that $p(S)\geq t(S)$ for every $S$ , with equality if and only if all points of $S$ are in convex position.

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