← All problems

The Number of Pointed Pseudotriangulations

25 years old · traced to

Let SS be a finite set of nn points in the plane. A triangulation of SS is a straight-line partition of its convex hull into triangles whose vertex set is exactly SS. 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 SS partitions its convex hull into pseudotriangles using exactly the vertices in SS. A pointed pseudotriangulation is one with the fewest possible edges among pseudotriangulations of SS; equivalently, it is a pseudotriangulation in which every vertex has an incident angle greater than π\pi. Write T(S)\mathcal{T}(S) for the set of triangulations and PPT(S)\mathcal{PPT}(S) for the set of pointed pseudotriangulations. The question is whether, for every such SS, Open Problems Project, Problem 40 On the Number of Pseudo-Triangulations of Certain Point Sets

∣PPT(S)∣≥∣T(S)∣?|\mathcal{PPT}(S)|\geq |\mathcal{T}(S)|?

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

References

Progress summary

Never refreshed

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.