12.12.2005

In this paper we present 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. We also present a space efficient dynamic data structure with O(log n/log log n + klog log n) query time that uses O(nlog log n) space. These are the first dynamic data structures with sublogarithmic query time for that problem.