ALCOMFT-TR-01-35

Stephen Alstrup, Gerth Stølting Brodal and Theis Rauhe
New Data Structures for Orthogonal Range Searching
Århus. Work package 4. April 2001.

Abstract: 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+epsilon 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 x n grid, we achieve query time O(log log n+ k) using space O(n log^epsilon n). For the two-dimensional semi-group range sum problem we achieve query time O(log n) using space O(n log n).

Postscript file: ALCOMFT-TR-01-35.ps.gz (183 kb).