A Parallel Method for the Prefix Convex Hulls Problem

Wei CHEN  Koji NAKANO  Toshimitsu MASUZAWA  Nobuki TOKURA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A   No.10   pp.1675-1683
Publication Date: 1994/10/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms, Data Structures and Computational Complexity
computational geometry,  convex hull problems,  optimal parallel algorithms,  the CREW PRAM model,  

Full Text: PDF>>
Buy this Article

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(logn) time using n/logn processors in the CREW PRAM computational model. The algorithm is shown to be time and cost optimal. One of the techniques we adopt to achieve these optimal bounds is the use of a new parallel data structure Array-Tree.