A Fast Las Vegas Algorithm for Triangulating a Simple Polygon
Report ID: TR-157-88Author: Clarkson, Kenneth L. / Tarjan, Robert E. / Van Wyk, Christopher J.
Date: 1988-05-00
Pages: 14
Download Formats: |PDF|
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.