Cascading divide-and-conquer: A technique for designing parallel algorithms
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 151-160
- https://doi.org/10.1109/sfcs.1987.12
Abstract
We present techniques for parallel divide-and-conquer, resulting in improved parallel algorithms for a number of problems. The problems for which we give improved algorithms include intersection detection, trapezoidal decomposition (hence, polygon triangulation), and planar point location (hence, Voronoi diagram construction). We also give efficient parallel algorithms for fractional cascading, 3-dimensional maxima, 2-set dominance counting, and visibility from a point. All of our algorithms run in O(log n) time with either a linear or sub-linear number of processors in the CREW PRAM model.Keywords
This publication has 16 references indexed in Scilit:
- Optimal randomized parallel algorithms for computational geometryAlgorithmica, 1992
- Parallel processing for efficient subdivision searchPublished by Association for Computing Machinery (ACM) ,1987
- Efficient parallel solutions to some geometric problemsJournal of Parallel and Distributed Computing, 1986
- Parallel merge sortPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Efficient plane sweeping in parallelPublished by Association for Computing Machinery (ACM) ,1986
- An optimal parallel algorithm for integer sortingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Finding the maximum, merging, and sorting in a parallel computation modelJournal of Algorithms, 1981
- An Optimal Worst Case Algorithm for Reporting Intersections of RectanglesIEEE Transactions on Computers, 1980
- On Finding the Maxima of a Set of VectorsJournal of the ACM, 1975
- Parallelism in Comparison ProblemsSIAM Journal on Computing, 1975