Optimal Randomized Parallel Algorithms for Computational Geometry

A summary of the results achieved in the paper "Optimal Randomized Parallel Algorithms for Computational Geometry," by Reif and Sen is given. These results include optimal randomized PRAM algorithms for the construction of Kirkpatrick's point location structure, and the construction of a data structure called a nested plane sweep tree. The plane sweep tree is used to solve a number of popular computational geometry problems optimally. All results hold with high probability. 1 Introduction Parallel algorithms for computational geometry problems have received much attention from the algorithms community in recent years. Many of these algorithms make use of randomization to make the problems tractable. In [ReSe92] Reif and Sen present a number of randomized algorithms for computational geometry problems which run in logarithmic time using a linear number of processors. Most of these algorithms are based on a data structure which the authors call a nested plane sweep tree. The goal of thi..