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 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 (this is optimal),
• a pyramid, binary tree, or mesh-of-trees that takes Θ((log³ n)/(log log n)²) time, and
• a reconfigurable mesh takes Θ(log² n) time.
• a CREW PRAM takes Θ(log n) time.

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 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 network, computational geometry, EREW PRAM, hypercube, mesh, mesh-of-trees, reconfigurable mesh, pyramid, 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-2012 Quentin F. Stout.