Abstract

We studyscalable parallel computational geometry algorithms for the coarse grained multicomputer model: p processors solving a problem on n data items, were each processor has O ( n) O(1) local memory and all processors are connected via some arbitrary p interconnection network (e.g. mesh, hypercube, fat tree). We present O ( Tsequential p Ts(n � p)) time scalable parallel algorithms for several computational geometry problems. Ts(n � p) refers to the time of a global sort operation. Our results are independent ofthemulticomputer's interconnection network. Their time complexities become optimal when Tsequential dominates Ts(n � p) or when Ts(n � p) p is optimal. This is the case for several standard architectures, including meshes and hypercubes, and a wide range of ratios n that include many of the currently available p machine con gurations. Our methods also have some important practical advantages: For interprocessor communication, they use only a small xed number of one global routing operation, global sort, and all other programming is in the sequential domain. Furthermore, our algorithms use only a small number of very large messages, which greatly reduces the overhead for the communication protocol between processors. (Note however, that our time complexities account for the lengths of messages.) Experiments show that our methods are easy to implement and give good timing results