12.12.2005

In this paper we present new results for planar and multi-dimensional orthogonal range reporting. We describe a dynamic data structure for planar orthogonal range reporting with query time O( log n/log log n + k) and space O(nlog^ε n) for any ε > 0 and k the answer size. This is the first dynamic data structures with sublogarithmic query time for that problem.
We also present a static data structure for three-dimensional range reporting queries with O(log n/log log n + k) query time. For three-dimensional range reporting on a U³ grid, we present a data structure with query time O((log log U)²log log log U + k log log U); this leads to three-dimensional range reporting in O((log n/log log n)^1/2+ klog log n) time. The last results can be extended to d-dimensional range reporting yielding also the best up to now query times for that case.
Our results depend on a new reductions method. This method could be of independent interest.