CASCADING DIVIDE-AND-CONQUER: A TECHNIQUE FOR DESIGNING PARALLEL ALGORITHMS.

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Techniques are presented for parallel divide-and-conquer, resulting in improved parallel algorithms for a number of problems, including intersection detection, trapezoidal decomposition (hence, polygon triangulation), and planar point location (hence, Voronoi diagram construction). Efficient parallel algorithms are also given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point. All of the algorithms run in O(log n) time with either a linear or sublinear number of processors in the concurrent-read-exclusive-write parallel random-access machine model.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages151-160
Number of pages10
ISBN (Print)0818608072, 9780818608070
DOIs
StatePublished - 1987

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

ASJC Scopus subject areas

  • Hardware and Architecture

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

    Atallah, M. J., Cole, R., & Goodrich, M. T. (1987). CASCADING DIVIDE-AND-CONQUER: A TECHNIQUE FOR DESIGNING PARALLEL ALGORITHMS. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 151-160). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE. https://doi.org/10.1109/sfcs.1987.12