Access Restriction

Author Bentley, Jon Louis
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Algorithmic paradigms ♦ Computational geometry ♦ Maxima problems ♦ Multidimensional searching problems ♦ Data structures ♦ Range searching ♦ Analysis of algorithms ♦ Empirical cumulative distribution functions ♦ Closest-point problem
Abstract Most results in the field of algorithm design are single algorithms that solve single problems. In this paper we discuss multidimensional divide-and-conquer, an algorithmic paradigm that can be instantiated in many different ways to yield a number of algorithms and data structures for multidimensional problems. We use this paradigm to give best-known solutions to such problems as the ECDF, maxima, range searching, closest pair, and all nearest neighbor problems. The contributions of the paper are on two levels. On the first level are the particular algorithms and data structures given by applying the paradigm. On the second level is the more novel contribution of this paper: a detailed study of an algorithmic paradigm that is specific enough to be described precisely yet general enough to solve a wide variety of problems.
Description Affiliation: Carnegie-Mellon Univ., Pittsburgh, PA (Bentley, Jon Louis)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 23
Issue Number 4
Page Count 16
Starting Page 214
Ending Page 229

Open content in new tab

   Open content in new tab
Source: ACM Digital Library