New data structures for orthogonal range searching

We present new general techniques for static orthogonal range searching problems in two and higher dimensions. For the general range reporting problem in R³, we achieve query time O(log n+k) using space O(n log^1+ε n), where n denotes the number of stored points and k the number of points to be reported. For the range reporting problem on an n×n grid, we achieve query time O(log log n+k) using space O(n log^ε n). For the two-dimensional semi-group range sum problem we achieve query time O(log n) using space O(n log n)