Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
Mikhail J. Atallah, Richard Cole, Michael T. Goodrich · SIAM Journal on Computing · 1989
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.