Polygon triangulation in O(n log log n) time with simple data structures

David G. Kirkpatrick, Maria M. Klawe, Robert Endre Tarjan

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

We give a new O(n log log n)-time deterministic algorithm for triangulating simple n-vertex polygons, which avoids the use of complicated data structures. In addition, for polygons whose vertices have integer coordinates of polynomially bounded size, the algorithm can be modified to run in O(n log*n) time. The major new techniques employed are the efficient location of horizontal visibility edges that partition the interior of the polygon into regions of approximately equal size, and a linear-time algorithm for obtaining the horizontal visibility partition of a subchain of a polygonal chain, from the horizontal visibility partition of the entire chain. The latter technique has other interesting applications, including a linear-time algorithm to convert a Steiner triangulation of a polygon into a true triangulation.

Original languageEnglish (US)
Pages (from-to)329-346
Number of pages18
JournalDiscrete & Computational Geometry
Volume7
Issue number1
DOIs
StatePublished - Dec 1 1992

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 'Polygon triangulation in O(n log log n) time with simple data structures'. Together they form a unique fingerprint.

  • Cite this