A Fast Las Vegas Algorithm for Triangulating a Simple Polygon

Report ID: TR-132-88

---

Author: Clarkson, Kenneth L. / Tarjan, Robert E. / Van Wyk, Christopher J.

---

Date: 1988-01-00

---

Pages: 10

---

Download Formats: |PDF|

---

Abstract:

We show how to use random sampling to triangulate a simple polygon in nearly linear expected time.