Skip to main content

OPTIMAL RANDOMIZED PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY.

Publication ,  Journal Article
Reif, JH; Sen, S
Published in: Proceedings of the International Conference on Parallel Processing
December 1, 1987

The authors present parallel algorithms for some fundamental problems in computational geometry which have optimal running time with very high probability (approaching 1 as n yields infinity ). These include planar point location, triangulation, trapezoidal decomposition, 3-D maxima, two-set dominance counting, and range-counting, among others. Most of these algorithms run on the CREW PRAM model with O(n) processors and execute in O(log n) time. Most of these algorithms use a novel data structure called the nested plane sweep tree. Random splitting is used very effectively to divide and conquer on the plane, raising the possibility of extending this technique to higher dimensions.

Duke Scholars

Published In

Proceedings of the International Conference on Parallel Processing

ISSN

0190-3918

Publication Date

December 1, 1987

Start / End Page

270 / 277
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Sen, S. (1987). OPTIMAL RANDOMIZED PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY. Proceedings of the International Conference on Parallel Processing, 270–277.
Reif, J. H., and S. Sen. “OPTIMAL RANDOMIZED PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY.Proceedings of the International Conference on Parallel Processing, December 1, 1987, 270–77.
Reif JH, Sen S. OPTIMAL RANDOMIZED PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY. Proceedings of the International Conference on Parallel Processing. 1987 Dec 1;270–7.
Reif, J. H., and S. Sen. “OPTIMAL RANDOMIZED PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY.Proceedings of the International Conference on Parallel Processing, Dec. 1987, pp. 270–77.
Reif JH, Sen S. OPTIMAL RANDOMIZED PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY. Proceedings of the International Conference on Parallel Processing. 1987 Dec 1;270–277.

Published In

Proceedings of the International Conference on Parallel Processing

ISSN

0190-3918

Publication Date

December 1, 1987

Start / End Page

270 / 277