A simple aggregative algorithm for counting triangulations of planar point sets and related problems

Abstract

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.