In IEEE Trans. Computers C-37 (1988), pp. 1605-1618.

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

Abstract: In this paper, we present parallel algorithms to identify (i.e., detect and enumerate) the extreme points of a set of planar points using a hypercube, pyramid, tree, mesh-of-trees, mesh with reconfigurable bus (rmesh), EREW PRAM, and a modified AKS network. It is known that the problem of identifying the convex hull for a set of planar points given arbitrarily cannot be solved faster than sorting. For the situation where the input set of n points is given ordered (by x-coordinate) one per processor on a machine with Theta(n) processors, we introduce an optimal hypercube algorithm that finishes in Theta(log n) time, an algorithm for the pyramid, tree, and mesh-of-trees that finishes in Theta((log3 n)/(log log n)2) time, and an algorithm for the reconfigurable mesh that finishes in Theta(log2 n) time. Notice that for ordered input the sorting bound does not apply.

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

IEEE has digitized this paper and made it available.
Paper.pdf (PDF) (Postscript) (compressed Postscript)

Russ Miller (