A simple aggregative algorithm for counting triangulations of planar point sets and related problems
Víctor Álvarez, Raimund Seidel · 2013
We give an algorithm that determines the number (S) of straight line triangulations of a set S of n points in the plane in worst case time O(n2 2n). This is the the first algorithm that is provably faster than enumeration, since (S) is known to be Ω(2.43n) for any set S of n points. Our algorithm requires exponential space.