A Fast Las Vegas Algorithm for Triangulating a Simple Polygon

Abstract:

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.