The Number of Pointed Pseudotriangulations
Let be a finite set of points in the plane. A triangulation of is a straight-line partition of its convex hull into triangles whose vertex set is exactly . A pseudotriangle is a planar polygon with exactly three convex vertices; the boundary between each pair of these vertices is a reflex chain, possibly a single segment. A pseudotriangulation of partitions its convex hull into pseudotriangles using exactly the vertices in . A pointed pseudotriangulation is one with the fewest possible edges among pseudotriangulations of ; equivalently, it is a pseudotriangulation in which every vertex has an incident angle greater than . Write for the set of triangulations and for the set of pointed pseudotriangulations. The question is whether, for every such , Open Problems Project, Problem 40 On the Number of Pseudo-Triangulations of Certain Point Sets
The question as stated imposes no general-position hypothesis. Open Problems Project, Problem 40
Background
Pseudotriangulations generalize ordinary triangulations by allowing faces with reflex boundary chains. They arose in work on visibility and ray shooting, and later found applications including kinetic collision detection and guarding; they also connect with rigidity and locally convex functions. Their flip structure is notably well behaved: the cited research describes a polytope whose vertices encode pseudotriangulations and whose edges correspond to flips. The counting question originated in work on wheels and was posed by Jack Snoeyink at the 2001 Canadian Conference on Computational Geometry open-problem session. On the Number of Pseudo-Triangulations of Certain Point Sets Open Problems Project, Problem 40
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.