The Number of Pointed Pseudotriangulations

Research-attempt provenance

Definitions and mathematical statement

Let $S\subset\mathbb R^2$ be a finite set of $n\ge3$ points with no three collinear. A straight-line triangulation of $S$ subdivides $\operatorname{conv}(S)$ into triangles using every point of $S$ as a vertex and no other vertices. Let $t(S)$ be its number of distinct triangulations, counted by their edge sets.

A pseudotriangle is a simple polygon with exactly three vertices whose interior angles are less than $\pi$; its remaining vertices are reflex. A pseudotriangulation of $S$ is a noncrossing straight-line subdivision of the same convex hull into pseudotriangles with vertex set exactly $S$. It is pointed when, at each vertex, all incident edge directions lie in an open angular interval of length $\pi$. Equivalently, some incident face sector has angle greater than $\pi$, including the exterior sector at a hull vertex.

Let $p(S)$ count pointed pseudotriangulations by their edge sets. The conjecture is \[ p(S)\ge t(S). \] The stronger equality assertion in the source predicts equality precisely when every point of $S$ is a vertex of its convex hull. Pointedness is required at all vertices, not merely at the three convex corners of each pseudotriangle.

Short English statement

Does every planar point set have at least as many pointed pseudotriangulations as ordinary triangulations, with equality only for points in convex position?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500040 (AMR-054-0040), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 40. Original source indexed by AMR-054-0040. https://topp.openproblem.net/p40.

Literature and context check

The consulted TOPP Problem 40 page records the inequality and the stronger equality assertion, as well as small-set verification. The calculations below are elementary checks of a possible counting proof, not a new counting bound.

Research attempt: Testing refinement as a counting injection

For convex-position $S$, any simple polygon whose vertices are a subset of $S$ in boundary order is convex. A bounded face of a noncrossing subdivision therefore has no reflex corner. If it is a pseudotriangle, it has exactly three vertices and is a triangle. Moreover at every hull vertex all incident edges lie within the hull's angle, strictly less than $\pi$. Thus pointed pseudotriangulations and triangulations coincide in this case.

The attempted proof for interior points was to remove edges from each triangulation until it becomes pointed, and claim different triangulations give different remnants. The following exact collision shows that refinement alone cannot justify injectivity. Set \[ A=(0,0),\ B=(6,0),\ C=(0,6),\ p=(1,2),\ q=(2,1). \] Let $H$ consist of the boundary edges $AB,BC,CA$ and the four edges $Ap,pC,Aq,qB$. Its bounded faces are triangles $AqB$ and $ACp$, and the pentagon with boundary $A,q,B,C,p$. In that pentagon, $A,B,C$ are convex and $p,q$ reflex, as is seen by the signed successive cross products; hence it is a pseudotriangle. At $p$ the two incident directions point strictly into the left half-plane, and at $q$ into the lower half-plane. Hull vertices are pointed automatically. Thus $H$ is a pointed pseudotriangulation.

The segment $pq$ lies in the central face and separates triangle $Apq$ from the convex quadrilateral $qBCp$. That quadrilateral can be triangulated either with $pB$ or with $qC$. Therefore \[ T_1=H\cup\{pq,pB\},\qquad T_2=H\cup\{pq,qC\} \] are distinct triangulations refining exactly the same pointed pseudotriangulation. The quadrilateral is strictly convex by the four orientation tests, so both refinements are legal. All five input points are in general position. Deleting the two specified edges from either $T_i$ gives $H$.

This does not prove that every possible edge-removal rule has collisions; a carefully designed global injection could choose different pointed outputs. It does prove that the mere existence of pointed subgraphs or triangulating each pseudotriangle cannot be counted as an injection. In a bipartite incidence graph between triangulations and their pointed subgraphs, positive degree on one side is insufficient to produce a matching. Even the two vertices $T_1,T_2$ may share a candidate neighbor, as here; proving a matching would need additional information about all their available neighbors.

The convex equality case and the explicit collision therefore leave both the general inequality and the strict inequality for every nonconvex-position set unproved. In particular counting refinements overcounts the triangulations in a way that cannot be discarded without a quantitative multiplicity argument.

Verification and adversarial audit

Exact Fraction arithmetic checked the ten triple determinants and found none zero. The seven edges, three bounded faces and two distinct refinements were checked explicitly; Euler's count $5-7+4=2$ includes the exterior face. Convex equality was proved directly and not extrapolated to interior vertices.

Audit corrections.

A shared refinement target was not treated as a counterexample to the inequality; it only defeats the unproved injectivity step.

External computation.

Exact Fraction determinant enumeration on the displayed five points: all ten determinants nonzero; command run in the session, no standalone computation script saved.

Scope and remaining gaps

The first gap is an injective choice of pointed subgraph, a matching theorem with its necessary neighbor bounds actually established, or another counting argument that controls these collisions. No such bound is proved here, and the equality characterization outside convex position remains part of the target.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://topp.openproblem.net/p40 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved. This is a research attempt with an explicit failed route or restricted calculation, not a full solution, not a current-status certification, and not a claim that the elementary material is new. The catalogue's original source-status label is preserved independently of this attempt status.