Indexing Moving Points
Pankaj K. Agarwal, Lars Arge, Jeff Erickson · 2000
) Pankaj K. Agarwal Lars Arge y Jeff Erickson z Abstract We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that a query of the following form can be answered quickly: Given a rectangle R and a real value tq , report all K points of S that lie inside R at time tq . We first present an indexing structure that, for any given constant " ? 0, uses O(N=B) disk blocks, where B is the block size, and answers a query in O((N=B) 1=2+" +K=B) I/Os. It can also report all the points of S that lie inside R during a given time interval. A point can be inserted or deleted, or the trajectory of a point can be changed, in O(log 2 B N) I/Os. Next, we present a general approach that improves the query time if the queries arrive in chronological order, by allowing the index to evolve over time. We obtain a tradeoff between the query time and the number of times the index needs to be updated as the points move. We also descri...