On the Number of Triangulations Every Planar Point Set Must Have

O. Aichholzer, F. Hurtado, and M. Noy

Abstract:

We show that the number of straight line triangulations exhibited by any set of $n$ points in general position in the plane is bounded from below by $\Omega((2+\varepsilon)^n)$ for some $\varepsilon > 0$. To the knowledge of the authors this is the first non-trivial lower bound.

Reference: O. Aichholzer, F. Hurtado, and M. Noy. On the number of triangulations every planar point set must have. In Proc. $13th$ Annual Canadian Conference on Computational Geometry CCCG 2001, pages 13-16, Waterloo, Ontario, Canada, 2001.