Convex Hull Parallel Algorithms

Efficient Parallel Convex Hull Algorithms

Russ Miller
Dept. of Computer Science, State University of New York at Buffalo

Quentin F. Stout
Computer Science and Engineering, University of Michigan

Abstract: We present parallel algorithms to enumerate the extreme points of a set of planar points. The parallel computers considered are the hypercube, pyramid, tree, mesh-of-trees, mesh with reconfigurable bus (rmesh), EREW PRAM, and a modified AKS sorting 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 real numbers. When the input set of n points is given in sorted order (by x-coordinate) one per processor on a machine with Θ(n) processors, our algorithms for

a hypercube takes Θ(log n) time,
a pyramid, binary tree, or mesh-of-trees take Θ((log³ n)/(log log n)²) time,
a reconfigurable mesh takes Θ(log² n) time, and
a CREW PRAM takes Θ(log n) time.

Notice that for ordered input the sorting bound does not apply, but the time for the hypercube is optimal since it equals the communication diameter.

The time for the CREW PRAM is achievable if the input is unsorted since the input can be sorted in O(log n) time. Thus for unsorted input it is optimal. 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 Θ(log n) time on a modified AKS sorting network, giving the first optimal Θ(log n) algorithm for solving the convex hull problem for arbitrary planar input on a fixed degree network with n processors. However, this is only of theoretical interest since the constants on the AKS network make it highly impractical.

In another paper we show that the convex hull can be determined in Θ(n^1/2) time on a 2-dimensional mesh-connected computer. This too is optimal, and that paper includes optimal algorithms for many other problems as well. Many of these easily extend to optimal algorithms on d-dimensional meshes, taking Θ(n^1/d) time, where the implied constants depend upon d. Optimal algorithms for the pyramid, tree, mesh-of-trees, and reconfigurable mesh are open problems.

If the points are chosen uniformly and independently from the unit square then the convex hull can be found in Θ(1) expected time using a CRCW PRAM with a weak concurrent write (either common write or collision detection). This is true even if the points are not sorted in advance. For such input fast expected case algorithms can also be developed for the pyramid, binary tree, mesh-of-trees, and reconfigurable mesh.

Keywords: parallel computer, convex hull, AKS sorting network, computational geometry, EREW PRAM, hypercube, mesh connected computer, mesh-of-trees, reconfigurable mesh, pyramid computer, parallel algorithm

Complete paper. It appears in IEEE Trans. Computers C-37 (1988), pp. 1605-1618.

Related work:
A modest explanation of parallel computing, a tutorial, Parallel Computing 101, and a list of parallel computing resources.
An overview of our work, and relevant papers.