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