2010/02/18 by Marek Karpiński, J. Ian Munro, Karpinski, Marek +3
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1002.3511
openalex publication_date 2010/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(√(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.