
University of Bonn > Department of Computer Science > Chair V  
CSReports 2008  Copyright 2008 University of Bonn, Department of Computer Science, Abt. V  
85292 24.07.08 
SpaceEfficient MultiDimensional Range Reporting
Marek Karpinski, Yakov Nekrich [Download PostScript] [Download PDF] We present a data structure that supports threedimensional 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 ddimensional 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
Deutsch 
University of Bonn > Department of Computer Science > Chair V 