Range searching in low-density environments
| Author(s) : | Jules Vleugels Otfried Schwarzkopf, |
| Publisher : | N/A |
| Publication Date : | 1996 |
| ISSN : | N/A |
| Abstract : | to be a lowdensity environment if any axis-parallel hypercube intersects only few objects of comparable or larger size. Generalizing and simplifying previous results for fat objects, we present a data structure for point location 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. Key words: computational geometry, point location, range, |