Lower Bounding the Number of Straight-Edge Triangulations of Planar Point Sets
Paul McCabe, Raimund Seidel · MPG.PuRe (Max Planck Society) · 2003
We examine the number of triangulations that any set of n points in the plane must have, and prove that (i) any set of n points has at least 0.00037*2.2n triangulations, (ii) any set with three extreme points and n interior points has at least 0.112*2.569n triangulation, and (iii) any set with n interior points has at least 0.238 * 2.38n triangulation. The best previously known lower bound for the number of triangulations for n points in the plane is 0.0822 * 2.0129n. We also give a method of automatically extending known bounds for small point sets to general lower bounds.