Range Reporting for Moving Points on a Grid

Details Range Reporting for Moving Points on a Grid Range Reporting for Moving Points on a Grid

2010-02-18

arxiv.org/abs/1002.3511v1

Computer Science

Data Structures and Algorithms

14 pages

Scientific paper

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\times U$ grid. The assumption that points lie on a $U\times 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 $\Omega(\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.

Affiliated with

Also associated with

No associations

Rating

Range Reporting for Moving Points on a Grid does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Range Reporting for Moving Points on a Grid, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Range Reporting for Moving Points on a Grid will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-405798