非表示:
キーワード:
-
要旨:
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 >0, an approximate range query treats the
range as a fuzzy object, meaning that points lying within distance w of the
boundary of Q either may or may not be counted. We show that in any fixed
dimension d, a set of n points in can be preprocessed in O(n+logn) time and
O(n) space, such that approximate queries can be answered in O(logn(1/)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(logn+(1/)d-1) time. We also
present a lower bound for approximate range searching based on partition trees
of (logn+(1/)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.
