Counting triangulations approximately

We consider the problem of counting straight-edge triangulations of a given set P of n points in the plane. Until very recently it was not known whether the exact number of triangulations of P can be computed asymptotically faster than by enumerating all triangulations. We now know that the number of triangulations of P can be computed in O∗(2ⁿ) time [2], which is less than the lower bound of Ω(2.43ⁿ) on the number of triangulations of any point set [11]. In this paper we address the question of whether one can approximately count triangulations in sub-exponential time. We present an algorithm with sub-exponential running time and subexponential approximation ratio, that is, if we denote by cⁿ the output of our algorithm, and by cn the exact number of triangulations of P, for some positive constant c, we prove that cⁿ ≥ Λ ≥ cⁿ · 2^o(ⁿ). This is the first algorithm that in sub-exponential time computes a (1 + o(1))-approximation of the base of the number of triangulations, more precisely, c ≥ Λ 1/n ≥ (1 + o(1))c. Our algorithm can be adapted to approximately count other crossing-free structures on P, keeping the quality of approximation and running time intact. The algorithm may be useful in guessing, through experiments, the right constants c1 and c2 such that the number of triangulations of any set of n points is between cⁿ₁ and cⁿ₂ . Currently there is a large gap between c₁ and c₂, we know that c1 ≥ 2.43 and c2 ≤ 30.