Carleton University
Technical Report TR-211
August 1992
Generating Triangulations at Random
Peter Epstein & Jörg-Rüdiger Sack
Abstract
An O(n3) algorithm is described to count triangulations of a simple polygon with n vertices. This algorithm is used to construct an O(n4) algorithm to generate triangulations of a simple polygon at random with a uniform probability distribution. As well, the problem of counting triangulations of a simple polygon is related to existing problems in graph theory.