Optimal randomized parallel algorithms for computational geometry


Journal Article

We present parallel algorithms for some fundamental problems in computational geometry which have a running time of O(log n) using n processors, with very high probability (approaching 1 as n → ∞). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach. © 1992 Springer-Verlag New York Inc.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Sen, S

Published Date

  • June 1, 1992

Published In

Volume / Issue

  • 7 / 1-6

Start / End Page

  • 91 - 117

Electronic International Standard Serial Number (EISSN)

  • 1432-0541

International Standard Serial Number (ISSN)

  • 0178-4617

Digital Object Identifier (DOI)

  • 10.1007/BF01758753

Citation Source

  • Scopus