2001 | OriginalPaper | Buchkapitel
Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM
verfasst von : Carla Denise Castanho, Wei Chen, Koichi Wada, Akihiro Fujiwara
Erschienen in: Computing and Combinatorics
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.