2014/11/03 by Marek Karpiński, Marek Karpinski, Karpinski, Marek +4
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #cs.CG
paper · pdf · doi:10.48550/arxiv.1411.0544
openalex publication_date 2014/11/03 · arxiv created 2014/11/20 · arxiv updated 2014/11/21 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
The number of triangulations of a planar n point set is known to be cn, where the base c lies between 2.43 and 30. The fastest known algorithm for counting triangulations of a planar n point set runs in O^*(2n) time. The fastest known arbitrarily close approximation algorithm for the base of the number of triangulations of a planar n point set runs in time subexponential in n. We present the first quasi-polynomial approximation scheme for the base of the number of triangulations of a planar point set.