O(n log log n)-time algorithm for triangulating a simple polygon

Robert E. Tarjan, Christopher J. Van Wyk

Research output: Contribution to journalArticlepeer-review

114 Scopus citations

Abstract

Given a simple n-vertex polygon, the triangulation problem is to partition the interior of the polygon into n-2 triangles by adding n-3 nonintersecting diagonals. We propose an O(n log log n)-time algorithm for this problem, improving on the previous best bound of O(n log n) and showing that triangulation is not as hard as sorting Improved algorithms for several other computational geometry problems, including testing whether a polygon is simple, follow from our result.

Original languageEnglish (US)
Pages (from-to)143-178
Number of pages36
JournalSIAM Journal on Computing
Volume17
Issue number1
DOIs
StatePublished - Jan 1 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'O(n log log n)-time algorithm for triangulating a simple polygon'. Together they form a unique fingerprint.

Cite this