OPTIMAL RANDOMIZED PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY.

Published

Journal Article

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 Authors

Cited Authors

  • Reif, JH; Sen, S

Published Date

  • December 1, 1987

Published In

Start / End Page

  • 270 - 277

International Standard Serial Number (ISSN)

  • 0190-3918

Citation Source

  • Scopus