For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 1994/10/25
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>>
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.