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

Notice that for ordered input the sorting bound does not apply.

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.

In another paper we show that the convex hull can be determined in Θ(n1/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. Optimal algorithms for the pyramid, tree, mesh-of-trees, and reconfigurable mesh are open problems.

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

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.

 


Quentin's Home Copyright © 2008-2016 Quentin F. Stout.