Optimal randomized parallel algorithms for computational geometry

Autor: H J Reif, Sandeep Sen
Rok vydání: 1992
Předmět:
Zdroj: Algorithmica. 7:91-117
ISSN: 1432-0541
0178-4617
DOI: 10.1007/bf01758753
Popis: We present parallel algorithms for some fundamental problems in computational geometry which have running time of $O(logn)$ using $n$ processors, with very high probability (approaching 1 as $n~ \rightarrow~ \infty$). These include planar point location, triangulation and trapezoidal decomposition. We also present optimal algorithms for 3-D maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on CREW PRAM model and have optimal processor-time product which improve on the previously best known algorithms of Atallah and Goodrich [3] 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 [22] Reif and Valiant [21] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach.
Databáze: OpenAIRE
Externí odkaz: