BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR92-183
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Concurrent Local Search for Fast Proximity Algorithms on Parallel and Vector Architectures
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Su, Peter
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1992
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR92-183.pdf
ABSTRACT::
	This paper presents a fast algorithm for solving the
all-nearest-neighbors problem. The algorithm uses a data parallel
style of programming which can be efficiently utilized on a variety of
parallel and vector architectures [4,21,26]. I have implemented the
algorithm in C on one such architecture, the Cray Y-MP.  On one Cray
CPU, the implementation is about 19 times faster than a fast
sequential algorithm running on a Sparc workstation.
	The main idea in the algorithm is to divide the plane up into
a fixed grid of cells, or buckets.  When the points are well
distributed, the algorithm processes each query point, q, by searching
a small number of cells close to q.  Bentley, WEide and Yao first
presented this idea for conventional architectures [3], but the
technique works equally well on parallel and vector machines, leading
to a simple, efficient algorithm.
	We can also use the cell technique to solve a wide variety of basic computational problems such as finding 
closest pairs, sorting and constructing Voronoi diagrams and Delaunay triangulations.
END:: ncstrl.dartmouthcs//TR92-183