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

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


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
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope