Accession Number : ADA192321
Title : Parallel Solutions to Geometric Problems on the Scan Model of Computation.
Descriptive Note : Memorandum rept.,
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB
Personal Author(s) : Blelloch, Guy E ; Little, James J
PDF Url : ADA192321
Report Date : Feb 1988
Pagination or Media Count : 34
Abstract : This paper describes several parallel algorithms that solve geometric problems. The algorithms are based on a vector model of computation - the scan-model. 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 in this paper have been implemented on the Connection Machine, a highly parallel single instruction multiple data (SIMD) computer.
Descriptors : *ALGORITHMS, *PARALLEL PROCESSING, *VECTOR ANALYSIS, COMPUTATIONS, GEOMETRY, LINE OF SIGHT, LINES(GEOMETRY), PARALLEL ORIENTATION, SCANNING, SOLUTIONS(GENERAL), MATHEMATICAL MODELS, RECURSIVE FUNCTIONS, BINARY NOTATION
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE