Scalable 2D convex hull and triangulation algorithms for coarse grained multicomputers

In this paper we describe scalable parallel algorithms for building the convex hull and a triangulation of n coplanar points. These algorithms are designed for the coarse grained multicomputer model: p processors with O(n/p) >> O(1) local memory each, connected to some arbitrary interconnection network. They scale over a large range of values of n and p, assuming only that n greater than or equal to p(1 + epsilon) (epsilon > 0) and require time O((T-sequential/P) + T-s(n, p)), where T-s(n, p) refers to the time of a global sort of n data on ap processor machine. Furthermore, they involve only a constant number of global communication rounds. Since computing either 2D convex hull or triangulation requires time T-sequential = Theta(n log n) these algorithms either run in optimal time: Theta((n log n)/p), or in sort time, T-s(n, p), for the interconnection network in question. These results become optimal when T-sequential/P dominates T-s(n, p) or for interconnection networks like the mesh for which optimal sorting algorithms exist. (C) 1999 Academic Press.