Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2008 Copyright 2008 Universität Bonn, Institut für Informatik, Abt. V
85292

24.07.08

Space-Efficient Multi-Dimensional Range Reporting
Marek Karpinski, Yakov Nekrich
[Download PostScript] [Download PDF]

We present a data structure that supports three-dimensional range reporting queries in O( log log U + ( log log n)3 +k) time and uses O(n log ε n) space, where U is the size of the universe, k is the number of points in the answer, and ε is an arbitrary constant. This result improves over the data structure of Alstrup, Brodal, and Rauhe (FOCS 2000) and the data structure of Nekrich (SoCG'07). Our result allows us to significantly reduce the space usage of the fastest previously known static and incremental d-dimensional data structures, d ≥ 3, at a cost of increasing the query time by a negligible O( log log n) factor.

Last Change: 07/24/08 at 16:25:04
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope