OPTIMAL PARALLEL RANDOMIZED ALGORITHMS FOR 3-DIMENSIONAL CONVEX HULLS AND RELATED PROBLEMS

作     者：REIF, JH SEN, S 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1992年第21卷第3期

页      面：466-485页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：CONVEX-HULLS PARALLEL ALGORITHMS RANDOMIZATION COMPUTATIONAL GEOMETRY 

摘      要：Further applications of random sampling techniques which have been used for deriving efficient parallel algorithms are presented by J. H. Reif and S. Sen [Proc. 16th International Conference on Parallel Processing, 1987). This paper presents an optimal parallel randomized algorithm for computing intersection of half spaces in three dimensions. Because of well-known reductions, these methods also yield equally efficient algorithms for fundamental problems like the convex hull in three dimensions, Voronoi diagram of point sites on a plane, and Euclidean minimal spanning tree. The algorithms run in time T = O(log n) for worst-case inputs and use P = O(n) processors in a CREW PRAM model where n is the input size. They are randomized in the sense that they use a total of only polylogarithmic number of random bits and terminate in the claimed time bound with probability 1 - n(-alpha) for any fixed alpha 0. They are also optimal in P.T product since the sequential time bound for all these problems is OMEGA(n log n). The best known deterministic parallel algorithms for two-dimensional Voronoi-diagram and three-dimensional convex hull run in O(log2 n) and O(log2 n log* n) time, respectively, while using O(n/log n) and O(n) processors, respectively.