1994/07/01 by Peter Epstein, Jörg-Rüdiger Sack · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Advanced Graph Theory Research #Combinatorics #Polygon (computer graphics) #Simple (philosophy) #Simple polygon #Polygon covering #Mathematics #Rectilinear polygon #Random graph #Discrete mathematics #Graph #Algorithm #Computer science #Monotone polygon #Geometry
paper · doi:10.1145/189443.189446
openalex publication_date 1994/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
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.