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