**Efficient Parallel Convex Hull Algorithms**

Russ Miller

Dept of Comp Sci & Eng, State University of New York at Buffalo

Quentin F. Stout

EECS Department, University of Michigan

We also show that our hypercube algorithm for ordered input extends to
yields an optimal *Theta(log n)* EREW PRAM algorithm for the case
where the points are ordered arbitrarily, one per processor. Previous
PRAM algorithms were either slower or required concurrent read or write
operations. We also show that this algorithm
can be extended to run in *Theta(log n)* time on a modified AKS
network, giving the first optimal *Theta(log n)* algorithm for
solving the convex hull problem for arbitrary planar input on a fixed
degree network with *n* processors.

**Keywords:** parallel computer,
AKS network, computational geometry, convex hull, EREW PRAM,
hypercube, mesh, mesh-of-trees, reconfigurable mesh, pyramid, parallel
algorithms, divide-and-conquer, discrete mathematics, computer science

Paper.pdf (PDF) Paper.ps (Postscript) Paper.ps.Z (compressed Postscript)

Russ Miller (miller@cse.buffalo.edu)