W. Chen et al., A PARALLEL METHOD FOR THE PREFIX CONVEX HULLS PROBLEM, IEICE transactions on fundamentals of electronics, communications and computer science, E77A(10), 1994, pp. 1675-1683
Citations number
NO
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
Given a sorted set S of n points in the plane, the prefix convex hulls
problem of S is to compute the convex hull for every prefix set of S.
We present a parallel algorithm for this problem. Our algorithm runs
in O(log n) time using n/log n processors in the CREW PRAM computation
al model. The algorithm is shown to be time and cost optimal. One of t
he techniques we adopt to achieve these optimal bounds is the use of a
new parallel data structure Array-Tree.