Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2005 Copyright 2005 University of Bonn, Department of Computer Science, Abt. V
85272

12.12.2005

Fast Data Structures for Orthogonal Range Reporting
Marek Karpinski and Yakov Nekrich
[Download PostScript] [Download PDF]

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 U3 grid, we present a data structure with query time O((log log U)2log 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.

Last Change: 12/13/05 at 10:11:34
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V