Efficient parallel convex hull algorithms
Russ Miller, Quentin F. Stout · IEEE Transactions on Computers · 1988
Parallel algorithms are presented 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, exclusive-read-exclusive-write parallel random-access machine (EREW PRAM), and modified AKS network. It is shown that the problem of identifying the convex hull for a set of planar points given arbitrarily, cannot be solved faster than sorting.>