An Optimal Algorithm for Range Search on Multidimensional Points

Abstract

This paper proposes an efficient and novel method to address range search on multidimensional points in $\theta (t)$ time, where $t$ is the number of points reported in ${\Re }^k$ space. This is accomplished by introducing a new data structure, called BITS $k$d-tree. This structure also supports fast updation that takes $\theta (1)$ time for insertion and $O(\log n)$ time for deletion. The earlier best known algorithm for this problem is $O({\log }^{k}n+t)$ time in the pointer machine model.