A PARALLEL METHOD FOR THE PREFIX CONVEX HULLS PROBLEM

Authors
CHEN W NAKANO K MASUZAWA T TOKURA N
Citation
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
Journal title
IEICE transactions on fundamentals of electronics, communications and computer science → ACNP
ISSN journal
09168508
Volume
E77A
Issue
10
Year of publication
1994
Pages
1675 - 1683
Database
ISI
SICI code
0916-8508(1994)E77A:10<1675:APMFTP>2.0.ZU;2-3
Abstract
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.