May 1996, 136pp.
The objective of this report is a unified investigation of a wide range of computational geometry algorithms and the design of Bulk-Synchronous Parallel algorithms that behave better than the immediate simulations of the corresponding PRAM algorithms. We present a methodology for constructing parallel computational geometry algorithms that are transportable, ie architecture independent algorithms capable of delivering scalable performance for a multiplicity of parallel architectures. The method we describe is based on the Bulk-Synchronous Parallel (BSP) model of computation, which abstracts the characteristics of a parallel machine into three numerical parameters p, g, and L, that quantify, respectively, processors, communication throughput to computation throughput, and synchronization period. These parameters, together with the problem size, are used to measure the performance, and, consequently, the transportability of geometric algorithms across parallel machines having different values of these parameters. In this report we theoretically analyze the efficiency with which several important geometric computations can be performed on bulk-synchronous parallel architectures. The computational problems considered include sorting, merging, bucketing, searching, intersections, convex hulls, maxima, visibility, proximity, voronoi diagrams, and geometric optimization. An important distinction between the approach that we consider in this report and the previous approaches is that our approach does not depend upon any particular choice of parallel system family but is universally applicable to any parallel machine (ie, distributed memory system, shared memory multiprocessor, network of workstations).