Optimal parallel algorithms for point-set and polygon problems

Richard Cole, Michael T. Goodrich

Research output: Contribution to journalArticle

Abstract

In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimal T(n) * P(n) products, where T(n) is the time complexity and P(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.

Original languageEnglish (US)
Pages (from-to)3-23
Number of pages21
JournalAlgorithmica (New York)
Volume7
Issue number1
DOIs
StatePublished - 1992

Keywords

  • All nearest-neighbor problem
  • Computational geometry
  • Convex hull
  • Kernel problem
  • Parallel algorithms
  • Polygon

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Software
  • Safety, Risk, Reliability and Quality
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Optimal parallel algorithms for point-set and polygon problems'. Together they form a unique fingerprint.

  • Cite this