On Numbers of Pseudo-Triangulations

2012/10/26 by Moria Ben-Ner, Ben-Ner, Moria, André Schulz +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CG #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1210.7126

arxiv created 2012/10/26 · arxiv updated 2012/10/29

Abstract

We study the maximum numbers of pseudo-triangulations and pointed pseudo-triangulations that can be embedded over a specific set of points in the plane or contained in a specific triangulation. We derive the bounds O(5.45^N) and Ω(2.41^N) for the maximum number of pointed pseudo-triangulations that can be contained in a specific triangulation over a set of N points. For the number of all pseudo-triangulations contained in a triangulation we derive the bounds O^*(6.54^N) and Ω(3.30^N). We also prove that O^*(89.1^N) pointed pseudo-triangulations can be embedded over any specific set of N points in the plane, and at most 120^N general pseudo-triangulations.

Related

• A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations
• Computational Geometry Column 43
• Counting Triangulations of Planar Point Sets
• A better upper bound on the number of triangulations of a planar point set
• Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials