Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Quick Search
My eDoc
Session History
Support Wiki
Direct access to
document ID:

          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents

ID: 518155.0, MPI für Informatik / Algorithms and Complexity Group
Approximate range searching
Authors:Arya, Sunil; Mount, David M.
Date of Publication (YYYY-MM-DD):2000
Title of Journal:Computational Geometry
Issue / Number:3/4
Start Page:135
End Page:152
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.