2001 | OriginalPaper | Chapter
Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM
Authors : Carla Denise Castanho, Wei Chen, Koichi Wada, Akihiro Fujiwara
Published in: Computing and Combinatorics
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)€) (€ lt; 1) using P(n) processors such that T(n)×P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for P-complete problems. In this paper we consider two P-complete geometric problems in the plane. First we consider the convex layers problem of a set S of n points. Let k be the number of the convex layers of S. When 1 = k = n €/2 (0 lt; € lt; 1) we can ?nd the convex layers of S in O( n log n/p ) time using p processors, where 1 = p = n 1-€/2 . Next, we consider the envelope layers problem of a set S of n line segments. Let k be the number of the envelope layers of S. When 1 = k = n€/2 (0 lt; € lt; 1), we propose an algorithm for computing the envelope layers of S in O(na(n) log3np) time using p processors, where 1 = p = n 1-€/2 , and a(n) is the functional inverse of Ackermann’s function which grows extremely slowly. The computational model we use in this paper is the EREW-PRAM. Our ?rst algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.