We present a randomized algorithm that triangulates a simple polygon on n vertices in O(n log*n) expected time. The averaging in the analysis of running time is over the possible choices made by the algorithm; the bound holds for any input polygon.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics