Chains, Koch Chains, and Point Sets with many Triangulations

2022/03/15 by Rutschmann, Daniel, Wettstein, Manuel · 2 citations
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2203.07584

Abstract

We introduce the abstract notion of a chain, which is a sequence of n points in the plane, ordered by x-coordinates, so that the edge between any two consecutive points is unavoidable as far as triangulations are concerned. A general theory of the structural properties of chains is developed, alongside a general understanding of their number of triangulations. We also describe an intriguing new and concrete configuration, which we call the Koch chain due to its similarities to the Koch curve. A specific construction based on Koch chains is then shown to have Ω(9.08ⁿ) triangulations. This is a significant improvement over the previous and long-standing lower bound of Ω(8.65ⁿ) for the maximum number of triangulations of planar point sets.

Cited by

• A note on non-crossing path partitions in the plane
• On existence of a compatible triangulation with the double circle order type

Related

• Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials
• Counting Triangulations of Planar Point Sets
• On the number of drawings of a combinatorial triangulation
• A better upper bound on the number of triangulations of a planar point set
• Minimum number of partial triangulations