10.01.2005

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(log² 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(log^d-1 n + k), update time O(log^d n), and space O(n log^d-2+ε n) for any ε > 0.