Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2010 Copyright 2010 University of Bonn, Department of Computer Science, Abt. V
85310

19.02.2010

Range Reporting for Moving Points on a Grid
Marek Karpinski, J. Ian Munro, Yakov Nekrich
[Download PostScript] [Download PDF]

In this paper we describe a new data structure that supports orthogonal range reporting queries on a set of points that move along linear trajectories on a U × U grid. The assumption that points lie on a U × U grid enables us to significantly decrease the query time in comparison to the standard kinetic model. Our data structure answers queries in O(\sqrt{log U/ log log U}+k) time, where k denotes the number of points in the answer. The above improves over the Ω(log n) lower bound that is valid in the infinite-precision kinetic model. The methods used in this paper could be also of independent interest.

Last Change: 12/13/10 at 13:38:43
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V