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
85271

12.12.2005

Dynamic Planar Orthogonal Range Reporting
Marek Karpinski and Yakov Nekrich
[Download PostScript] [Download PDF]

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.

Last Change: 12/14/05 at 09:11:57
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V