Space efficient dynamic orthogonal range reporting
Yakov Nekrich · 2005
In this paper we present new space e cient dynamic data structures for orthogonal range reporting.The described data structures support planar range reporting queries in time O (log n +k log log(4 n/(k +1)))and space O (n log log n ), or in time O (log n+k )and space O (n log e n )for any e > 0. Both data structures can be constructed in O (n log n )time and support insert and delete operations in amortized time O (log 2 n )and O (log n log log n )respectively. These results match the corresponding upper space bounds of Chazelle [6] 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+e n )for any e > 0.