Authors : T. Hema and K.S. Easwarakumar
Abstract: This study proposes an efficient and novel method to address range search on multidimensional points in θ(t) time where t is the number of points reported in ℜk space. This is accomplished by introducing a new data structure, called BITS kd-tree. This structure also supports fast updation that takes θ(1) time for insertion and O(log n) time for deletion. The earlier best known algorithm for this problem is O(logkn+t) time in the pointer machine model.
T. Hema and K.S. Easwarakumar, 2016. An Optimal Algorithm for Range Search on Multidimensional Points. Asian Journal of Information Technology, 15: 1723-1730.