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.

A typical range searching problem has the following form: Preprocess a set S of points in Rd 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 ( 15 Nov 1999