Convexity algorithms for parallel machines

The authors present a 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 (exclusive read, exclusive write parallel random-access machine) and AKS sorting network. For the situation where the input set of n planar points is given ordered one per processor on a machine with Θ(n) processors, the authors 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 Θ(log³ n/log logn)-time, and a worst-case algorithm for the mesh with reconfigurable bus that finishes in Θ(log² n) time. For the situation where the input set is given unordered one per processor, several optimal worst-case algorithms are given. It is shown that the Θ(log n) time hypercube algorithm for ordered data will extend to yield a worst-case optimal EREW PRAM algorithm and AKS sorting network algorithm for the case where the set of planar points is distributed in random fashion one point per processor