Triangulation and shape-complexity

B. Chazelle, J. Incerpi

Research output: Contribution to journalArticle

80 Scopus citations

Abstract

This paper describes a new method for triangulating a simple n-sided polygon. The algorithm runs in time O(n log s), with s ≥ n. The quantity s measures the sinuosity of the polygon, that is, the number of times the boundary alternates between complete spirals of opposite orientation. The value of s is in practice a very small constant, even for extremely winding polygons. Our algorithm is the first method whose performance is linear in the number of vertices, up to within a factor that depends only on the shape-complexity of the polygon. Informally, this notion of shape-complexity measures how entangled a polygon is, and is thus highly independent of the number of vertices. A practical advantage of the algorithm is that it does not require sorting or the use of any balanced tree structure. Aside from the notion of sinuosity, we are also able to characterize a large class of polygons for which the algorithm can be proven to run in O(n log log n) time. The algorithm has been implemented, tested, and empirical evidence has confirmed its theoretical claim to efficiency.

Original languageEnglish (US)
Pages (from-to)135-152
Number of pages18
JournalACM Transactions on Graphics (TOG)
Volume3
Issue number2
DOIs
StatePublished - Apr 1 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design

Keywords

  • Divide-and-conquer
  • shape-complexity
  • triangulation

Fingerprint Dive into the research topics of 'Triangulation and shape-complexity'. Together they form a unique fingerprint.

  • Cite this