New Data Structures for Orthogonal Range Queries

Abstract

Consider a set of N records corresponding to points in k-dimensional space ($k \geqq 2$). This article introduces one new data structure which uses memory $O(N\log ^{k - 1} N)$ for supporting orthogonal range queries with worst-case complexity $O(\log ^{k - 1} N)$ and several modifications of this proposal for a dynamic environment. These results are especially useful when $k = 2$.