Please use this identifier to cite or link to this item:

Approximate range searching

Authors Arya, Sunil View this author's profile
Mount, David M.
Issue Date 2000
Source Computational geometry-theory and Applications , v. 17, (3-4), 2000, Dec., p. 135-152
Summary The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show that if linear space is assumed, 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 particular, 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. We show that in any fixed dimension d, a set of n points in R-d can be preprocessed 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 ranges, 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 Omega (log n + (1/epsilon)(d-1)), which implies optimality for convex ranges (assuming fixed dimensions). Finally, we give empirical evidence showing that allowing small relative errors can significantly improve query execution times. (C) 2000 Elsevier Science B.V. All rights reserved.
ISSN 09257721
Language English
Format Technical report
Access View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
199910.pdf 336306 B Adobe PDF