A new linear algorithm for triangulating monotone polygons

Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review

Abstract

Let P = (p1, p2,...,pn) be a monotone polygon whose vertices are specified in terms of cartesian coordinates in order. A new simple two-step procedure is presented for triangulating P, without the addition of new vertices, in O(n) time. Unlike the previous algorithm no specialized code is needed since the new approach uses well-known existing algorithms for first decomposing P into edge-visible polygons and subsequently triangulating these.

Original languageEnglish (US)
Pages (from-to)155-158
Number of pages4
JournalPattern Recognition Letters
Volume2
Issue number3
DOIs
StatePublished - Mar 1984

Keywords

  • Algorithms
  • complexity
  • computational geometry
  • computer graphics
  • edge-visible polygons
  • image processing
  • monotone polygons
  • pattern recognition
  • polygon decomposition
  • simple polygons
  • triangulation
  • visibility

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'A new linear algorithm for triangulating monotone polygons'. Together they form a unique fingerprint.

Cite this