A fast las vegas algorithm for triangulating a simple polygon

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

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)423-432
Number of pages10
JournalDiscrete & Computational Geometry
Issue number1
StatePublished - Dec 1989

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'A fast las vegas algorithm for triangulating a simple polygon'. Together they form a unique fingerprint.

Cite this