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 setSof points inR^{d}so that the points inSlying 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