29.09.2014

The number of triangulations of a planar n point set is known to be cⁿ , 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^*(2ⁿ) 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.