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 -