TY - JOUR
T1 - Cascading divide-and-conquer
T2 - a technique for designing parallel algorithms
AU - Atallah, Mikhail J.
AU - Cole, Richard
AU - Goodrich, Michael T.
PY - 1989
Y1 - 1989
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0024681436&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0024681436&partnerID=8YFLogxK
U2 - 10.1137/0218035
DO - 10.1137/0218035
M3 - Article
AN - SCOPUS:0024681436
SN - 0097-5397
VL - 18
SP - 499
EP - 532
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 3
ER -