Key points are not available for this paper at this time.
We introduce a new technique for solving problems of the following form: preprocess a set of objects so that those satisfying a given property with respect to a query object can be listed very effectively. Well-known problems that fall into this category include range search, point enclosure, intersection, and near-neighbor problems. The approach which we take is very general and rests on a new concept called filtering search. We show on a number of examples how it can be used to improve the complexity of known algorithms and simplify their implementations as well. In particular, filtering search allows us to improve on the worst-case complexity of the best algorithms known so far for solving the problems mentioned above.
Bernard Chazelle (Fri,) studied this question.