Quick links

A Fast Las Vegas Algorithm for Triangulating a Simple Polygon

Report ID:
TR-157-88
Date:
April 1988
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.

Follow us: Facebook Twitter Linkedin