Cascading divide-and-conquer: a technique for designing parallel algorithms

Mikhail J. Atallah, Richard Cole, Michael T. Goodrich

Research output: Contribution to journalArticle

Abstract

Techniques for parallel divide-and-conquer are presented, resulting in improved parallel algorithms for a number of problems. The problems for which improved algorithms are given include segment intersection detection, trapezoidal decomposition, and planar point location. Efficient parallel algorithms are algo given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point. All of the algorithms presented run in O(log n) time with either a linear or a sublinear number of processors in the CREW PRAM model.

Original languageEnglish (US)
Pages (from-to)499-532
Number of pages34
JournalSIAM Journal on Computing
Volume18
Issue number3
DOIs
StatePublished - 1989

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Cascading divide-and-conquer: a technique for designing parallel algorithms'. Together they form a unique fingerprint.

  • Cite this