Abstract: 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 Θ(n) processors, we introduce an optimal hypercube algorithm that finishes in Θ(log n) time, an algorithm for the pyramid, tree, and mesh-of-trees that finishes in Θ((log³ n)/(log log n)²) time, and an algorithm for the reconfigurable mesh that finishes in Θ(log² 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 Θ(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 Θ(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.

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

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 Quentin F. Stout.