Kinetic medians and kd-trees

Published

Conference Paper

© Springer-Verlag Berlin Heidelberg 2002. 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 by a constant factor. 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(n1/n=€ ) 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 poly-logarithmic. To maintain the pseudo fcd-tree, we develop 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 in which there are speed-limit restrictions or smooth trajectory requirements. The maintenance of the pseudo fcd-tree, as a consequence of the approximate median algorithm, can also adapt to those restrictions.

Duke Authors

Cited Authors

  • Agarwal, PK; Gao, J; Guibas, LJ

Published Date

  • January 1, 2002

Published In

Volume / Issue

  • 2461 /

Start / End Page

  • 5 - 17

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540441808

International Standard Book Number 13 (ISBN-13)

  • 9783540441809

Citation Source

  • Scopus