Approximate range searching

The range searching problem is a fundamental problem in computational geome try, with numerous important applications. Most research has focused on sol ving this problem exactly, but lower bounds show that if linear space is as sumed, the problem cannot be solved in polylogarithmic time, except for the case of orthogonal ranges. In this paper we show that if one is willing to allow approximate ranges, then it is possible to do much better. In partic ular, given a bounded range Q of diameter w and epsilon > 0, an approximate range query treats the range as a fuzzy object, meaning that points lying within distance Ew of the boundary of e either may or may not be counted. W e show that in any fixed dimension d, a set of n points in R-d can be prepr ocessed in O(n + log n) time and O(n) space, such that approximate queries can be answered in O(log n(1/epsilon)(d)) time. The only assumption we make about ranges is that the intersection of a range and a d-dimensional cube can be answered in constant time (depending on dimension). For convex range s, we tighten this to O(log n + (1/epsilon )d(-1)) time. We also present a lower bound for approximate range searching based on partition trees of Ome ga (log n + (1/epsilon)(d-1)), which implies optimality for convex ranges ( assuming fixed dimensions). Finally, we give empirical evidence showing tha t allowing small relative errors can significantly improve query execution times. (C) 2000 Elsevier Science B.V. All rights reserved.