Triangulating a simple polygon in linear time

Research output: Contribution to journalArticle

416 Scopus citations

Abstract

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
Volume6
Issue number1
DOIs
StatePublished - Dec 1 1991

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Triangulating a simple polygon in linear time'. Together they form a unique fingerprint.

  • Cite this