P. K. Agarwal, J. Gao, L. J. Guibas, Kinetic Medians and kd-trees, Proc. of the 10th Annual European Symposium on Algorithms (ESA'02), Lecture Notes in Computer Science 2461, 5-16, September 2002.

Abstract:

We propose algorithms for maintaining two variants of $kd$-trees of a set of moving points in the plane. A pseudo $kd$-tree allows the number of points stored in the two children to differ. An overlapping $kd$-tree allows the bounding boxes of two children to overlap. We show that both of them support range search operations in $O(n^{1/2+\epsilon})$ time, where $\epsilon$ only depends on the approximation precision. When the points move, we use event-based kinetic data structures to update the tree when necessary. Both trees undergo only a quadratic number of events, which is optimal, and the update cost for each event is only polylogarithmic. To maintain the pseudo $kd$-tree, we make use of algorithms for computing an approximate median level of a line arrangement, which itself is of great interest. We show that the computation of the approximate median level of a set of lines or line segments, can be done in an online fashion smoothly, i.e., there are no expensive updates for any events. For practical consideration, we study the case when there are speed limit restrictions or smooth trajectory requirements. The maintenance of the pseudo $kd$-tree, as a consequence of the approximate median algorithm, can also adapt to those restrictions.

Bibtex: 

@inproceedings{agg-kmkd-02,
     author="P. K. Agarwal and J. Gao and L. J. Guibas", 
     title="Kinetic Medians and $kd$-trees", 
     booktitle="Proc. of the 10th Annual European Symposium on Algorithms (ESA'02)", 
     year="2002",
     pages="5--16", 
     month="September"
}