Generating triangulations at random
Peter Epstein, Jörg-Rüdiger Sack · ACM Transactions on Modeling and Computer Simulation · 1994
An O(n 3 ) algorithm is described to count triangulations of a simple polygon with n vertices. This algorithm is used to construct an O(n 4 ) algorithm to generate triangulations of a simple polygon at random with a uniform probability distribution. The problem of counting triangulations of a simple polygon is then related to existing problems in graph theory.