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

Abstract

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

6 pages, 1 figure

Cited by in corpus (10)

• Bounds on the maximum multiplicity of some common geometric graphs
• On the Number of Pseudo-Triangulations of Certain Point Sets
• Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness
• Counting Polygon Triangulations is Hard
• Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique
• The Flip Diameter of Rectangulations and Convex Subdivisions
• Counting Triangulations of Configurations
• Counting Triangulations and other Crossing-Free Structures Approximately
• On the Number of Higher Order Delaunay Triangulations
• Counting Triangulations of Planar Point Sets