TY - GEN

T1 - CASCADING DIVIDE-AND-CONQUER

T2 - A TECHNIQUE FOR DESIGNING PARALLEL ALGORITHMS.

AU - Atallah, Mikhail J.

AU - Cole, Richard

AU - Goodrich, Michael T.

PY - 1987

Y1 - 1987

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023589497&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023589497&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1987.12

DO - 10.1109/sfcs.1987.12

M3 - Conference contribution

AN - SCOPUS:0023589497

SN - 0818608072

SN - 9780818608070

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 151

EP - 160

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -