Triangulating a simple polygon in linear time

Research output: Contribution to journalArticlepeer-review

473 Scopus citations


We give a deterministic algorithm for triangulating a simple polygon in linear time. The basic strategy is to build a coarse approximation of a triangulation in a bottom-up phase and then use the information computed along the way to refine the triangulation in a top-down phase. The main tools used are the polygon-cutting theorem, which provides us with a balancing scheme, and the planar separator theorem, whose role is essential in the discovery of new diagonals. Only elementary data structures are required by the algorithm. In particular, no dynamic search trees, of our algorithm.

Original languageEnglish (US)
Pages (from-to)485-524
Number of pages40
JournalDiscrete & Computational Geometry
Issue number1
StatePublished - Dec 1991
Externally publishedYes

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 'Triangulating a simple polygon in linear time'. Together they form a unique fingerprint.

Cite this