24.07.08

We present a data structure that supports three-dimensional range reporting queries in O( log log U + ( log log n)³ +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.