Parallel solutions to geometric problems on the scan model of computation. Memorandum report
Guy E. Blelloch, James J. Little · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1988
This paper describes several parallel algorithms that solve geometric problems. The algorithms are based on a vector model of computation - the scanmodel. The purpose of this paper is both to show how the model can be used and to show a set of interesting algorithms. A k-D tree algorithm is described that, for n points, requires 0(1g n) calls to the primitives, a closets-pair algorithm that requires 0(1g n) calls to the primitives, a line-drawing algorithm that requires 0(1) calls to the primitives, a line-of-sight algorithm that requires 0(1) calls to the primitives, and finally three different convex-hull algorithms. All these algorithms should be noted for their simplicity rather than complexity; many of them are parallel versions of known serial algorithms. Most of the algorithms discussed have been implemented on the Connection Machine, a highly parallel single-instruction multiple data (SIMD) computer.