A Lower Bound on the Number of Triangulations of Planar Point Sets

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

Abstract:

We show that the number of straight-edge triangulations exhibited by any set of $n$ points in general position in the plane is bounded from below by $\Omega(2.33^n)$.

Reference: O. Aichholzer, F. Hurtado, and M. Noy. A lower bound on the number of triangulations of planar point sets. Computational Geometry: Theory and Applications, 29(2):135-145, 2004.