Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Arya, Sunil
Mount, David M.

dblp
dblp



BibTeX cite key*:

AryaMount2000

Title

Title*:

Approximate range searching

Journal

Journal Title*:

Computational Geometry

Journal's URL:

http://www.elsevier.nl/locate/comgeo

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.nl/

Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0925-7721

Vol, No, pp, Date

Volume*:

17

Number:

3/4

Publishing Date:

2000

Pages*:

135-152

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

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.

URL for the Abstract:


Categories,
Keywords:

Approximation algorithms, Box-decomposition trees, Partition trees, Range searching

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{AryaMount2000,
AUTHOR = {Arya, Sunil and Mount, David M.},
TITLE = {Approximate range searching},
JOURNAL = {Computational Geometry},
PUBLISHER = {Elsevier},
YEAR = {2000},
NUMBER = {3/4},
VOLUME = {17},
PAGES = {135--152},
ADDRESS = {Amsterdam, The Netherlands},
ISBN = {0925-7721},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Anja Becker
Created
03/14/2001 03:42:45 PM
Revisions
2.
1.
0.

Editor(s)
Uwe Brahm
Anja Becker
Anja Becker

Edit Dates
05/02/2001 11:31:59 AM
04.04.2001 15:52:07
14.03.2001 15:44:56