Geometric range searching and its relatives
Pankaj K. Agarwal, J. Craig Erickson · Contemporary mathematics - American Mathematical Society · 1999
. 1. Introduction HW Cl, Cl2 CS Pankaj K. Agarwal and Jeff Erickson Geometric Range Searching and Its Relatives Contemporary Mathematics c 0000 (copyright holder) Mathematics Subject Classification. Key words and phrases. Handbook of Discrete and Computational Geometry About ten years ago, the field of range searching, especially simplex range searching, was wide open. At that time, neither efficient algorithms nor nontrivial lower bounds were known for most range-searching problems. A series of papers by Haussler and Welzl [ ], Clarkson [ ], and Clarkson and Shor [ ] not only marked the beginning of a new chapter in geometric searching, but also revitalized computational geometry as a whole. Led by these and a number of subsequent papers, tremendous progress has been made in geometric range searching, both in terms of developing efficient data structures and proving nontrivial lower bounds. From a theoretical point of view, range searching is now almost completely solved. The imp...