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

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

10.01.2005

Space Efficient Dynamic Orthogonal Range Reporting
Yakov Nekrich
[Download PostScript] [Download PDF]

In this paper we present new space efficient dynamic data structures for orthogonal range reporting. The described data structures support planar range reporting queries in time O(log n + k log log(4n/(k + 1))) and space O(n log log n), or in time O(log n + k) and space O(n logε n) for any ε > 0. Both data structures can be constructed in O(n log n) time and support insert and delete operations in amortized time O(log2 n) and O(log n log log n) respectively. These results match the corresponding upper space bounds of Chazelle [Ch88] for the static case.
We also present a dynamic data structure for d-dimensional range reporting with search time O(logd-1 n + k), update time O(logd n), and space O(n logd-2+ε n) for any ε > 0.

Last Change: 03/03/05 at 10:21:34
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope