Kinetic kd-trees and longest-side kd-trees

We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of n points in Rd. We show that a rank-based kd-tree, like an ordinary kd-tree, supports orthogonal range queries in O(n1-1/d + k) time, where k is the output size. The main advantage of rank-based kd-trees is that they can be efficiently kinetized: the kinetic data structure (KDS) processes O(n2) events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in O(log n) time, and each point is involved in O(1) certificates. We also propose a variant of longest-side kd-trees, called rank-based longest-side kd-trees, for sets of points in R2. Rank-based longest-side kd-trees can be kinetized efficiently as well, and like longest-side kd-trees, they support e-approximate nearest-neighbor, e-approximate farthest-neighbor, and e-approximate range queries with convex ranges in O((1/e) log2 n) time. The KDS processes O(n3 log n) events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in O(log2 n) time, and each point is involved in O(log n) certificates.