RANGE SEARCHING IN LOW-DENSITY ENVIRONMENTS

Authors
SCHWARZKOPF O VLEUGELS J
Citation
O. Schwarzkopf et J. Vleugels, RANGE SEARCHING IN LOW-DENSITY ENVIRONMENTS, Information processing letters, 60(3), 1996, pp. 121-127
Citations number
10
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
60
Issue
3
Year of publication
1996
Pages
121 - 127
Database
ISI
SICI code
0020-0190(1996)60:3<121:RSILE>2.0.ZU;2-8
Abstract
We define a set of arbitrarily-shaped objects in R(d) to be a low-dens ity environment if any axis-parallel hypercube intersects only few obj ects of comparable or larger size. Generalizing and simplifying previo us results for fat objects, we present a data structure for point loca tion in a low-density environment, and we show how this data structure can be extended to perform range search queries with query ranges of size comparable to the smallest object.