Efficient Parallel Convex Hull Algorithms

In this paper, we present parallel algorithms to identify (i.e., detect and enumerate) the extreme points of the convex hull of a set of planar points using a hypercube, pyramid, tree, mesh-of-trees, mesh with reconfigurable bus, 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 planar points is given ordered (by x-coordinate) one per processor on a machine with θ(n) processors, we introduce a worst case hypercube algorithm that finishes in θ(log n) time, a worst case algorithm for the pyramid, tree, and mesh-of-trees that finishes in θ(log3n/(log log n)2) time, and a worst case algorithm for the mesh with a reconfigurable bus that finishes in θ(log2n) time. Notice that for ordered data the sorting bound does not apply. We also show that our θ(log n) time hypercube algorithm for ordered data extends to yield an optimal time and processor θ(log n) worst case time EREW PRAM algorithm for the case where the set of planar points is distributed arbitrarily one point per processor. We also show that this algorithm can be extended to run in worst case θ(log n) time on a modified AKS network, giving the first optimal θ(log n) time algorithm for solving the convex hull problem for arbitrary planar input on a fixed degree network.