Parallel triangulation of a polygon in two calls to the trapezoidal map

Research output: Contribution to journalArticle

Abstract

We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interesting partition of one-sided monotone polygons. Using the best-known trapezoidal map algorithm, ours run in time O(log n) using O(n) CREW PRAM processors.

Original languageEnglish (US)
Pages (from-to)279-288
Number of pages10
JournalAlgorithmica
Volume3
Issue number1
DOIs
StatePublished - Mar 1988

Keywords

  • Parallel algorithm
  • Polygon
  • Triangulation

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Parallel triangulation of a polygon in two calls to the trapezoidal map'. Together they form a unique fingerprint.

  • Cite this