k-dimensional orthogonal range search with tries
We present an algorithm using tries to solve the orthogonal range search problem on k dimensions. The algorithm reports all k-d hyper-rectangles intersecting a k-d axis-aligned query hyper-rectangle W, and supports dynamic operations. For the input data set D and W drawn from a uniform, random distribution, we analyse the expected time for orthogonal range search. We show that the storage S(n, k) =O(nk), and the expected preprocessing time P(n, k) = O(nk) for a trie containing n k-d hyper-rectangles.