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
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 Θ(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. 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.
Copyright © 2008-2016 Quentin F. Stout. |