Geometric range searching and its relatives

Written with Pankaj K. Agarwal.
Advances in Discrete and Computational Geometry
(Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, editors)
Contemporary Mathematics 223, American Mathematical Society Press, 1999, pages 1-56.

Technical Report CS-1997-11, Duke University, June 1997; revised September 1997.

Download final version (© 1998 AMS):
Download revised technical report:
See also Pankaj's shorter survey in the CRC Handbook of Discrete and Computational Geometry
According to ResearchIndex, this is one of the 50 most cited computer science papers published in 1999!

Abstract:
A typical range searching problem has the following form: Preprocess a set S of points in R^d so that the points in S lying inside a query range can be reported or counted quickly. We survey the known techniques and data structures for range searching and describe their applications to other related searching problems.

Figure 1. An offline semigroup algorithm to compute the weight of the points in each disk.

Figure 7. Trading space for query time by combining two decomposition schemes.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 15 Nov 1999