Counting Triangulations of Planar Point Sets

2009/11/17 by Micha Sharir, Sharir, Micha, Adam Sheffer +1 · 2 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Computational Geometry and Mesh Generation #Data Management and Algorithms #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2

paper · pdf · doi:10.48550/arxiv.0911.3352

openalex publication_date 2009/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the maximal number of triangulations that a planar set of n points can have, and show that it is at most 30ⁿ. This new bound is achieved by a careful optimization of the charging scheme of Sharir and Welzl (2006), which has led to the previous best upper bound of 43ⁿ for the problem. Moreover, this new bound is useful for bounding the number of other types of planar (i.e., crossing-free) straight-line graphs on a given point set. Specifically, we derive new upper bounds for the number of planar graphs (o(239.4ⁿ)), spanning cycles (O(70.21ⁿ)), and spanning trees (160ⁿ).

Cited by

• Further analysis of Peeling Sequences
• A note on non-crossing path partitions in the plane

Related

• New Properties of Numbers of Plane Graphs
• A better upper bound on the number of triangulations of a planar point set
• On the number of drawings of a combinatorial triangulation
• Counting Lattice Triangulations
• Counting Triangulations and other Crossing-free Structures via Onion Layers