TR-211: Generating Triangulations at Random
杏吧原创 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.