We also show that our hypercube algorithm for ordered input extends to yields an optimal Theta(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 Theta(log n) time on a modified AKS network, giving the first optimal Theta(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, discrete mathematics, computer science