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 a given point set in R ². 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 (e.g. mesh, hypercube, omega). They 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 a p 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=Θ(n log n n) these algorithms either ran in optimal time, Θ(^{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), for instance when randomized sorting algorithms are used, or for interconnection networks like the mesh for which optimal sorting algorithms exist