A better upper bound on the number of triangulations of a planar point set

2002/04/18 by Francisco Santos, Raimund Seidel
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #math.CO #msc:05C10

paper · pdf · doi:10.1016/s0097-3165(03)00002-5

published as J. Combin. Theory Ser. A, 102:1 (2003), 186-193 · 6 pages, 1 figure

arxiv created 2002/04/18 · openalex publication_date 2003/04/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

We show that a point set of cardinality n in the plane cannot be the vertex set of more than 59ⁿ O(n^-6) straight-edge triangulations of its convex hull. This improves the previous upper bound of 276.75ⁿ.

Related

• Counting Triangulations of Planar Point Sets
• Minimum number of partial triangulations
• Counting Triangulations of Fixed Cardinal Degrees
• Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials
• A QPTAS for the Base of the Number of Triangulations of a Planar Point\n Set