Parallel Solutions to Geometric Problems on the Scan Model of Computation.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1988
Accession Number
ADA192321

Entities

People

  • Guy E. Blelloch
  • James J. Little

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computations
  • Geometry
  • Information Systems
  • Line Of Sight
  • Military Research
  • Parallel Computing
  • Splitting
  • Trees (Data Structures)
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Computer Vision.
  • Parallel and Distributed Computing.