New Data Structures for Orthogonal Range Searching

Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe

Technical Report, ALCOMFT-TR-01-35, ALCOM-FT, 17 pages, May 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 R3, we achieve query time O(log n +k) using space O(n log1+ε 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ε n). For the two-dimensional semi-group range sum problem we achieve query time O(log n) using space O(n log n).

Online version

alcomft-tr-01-35.pdf (199 Kb)

BIBTEX entry

@techreport{alcomft-tr-01-35,
  author = "Stephen Alstrup and Gerth St{\o}lting Brodal and Theis Rauhe",
  institution = "ALCOM-FT",
  month = "May",
  number = "ALCOMFT-TR-01-35",
  pages = "17",
  title = "New Data Structures for Orthogonal Range Searching",
  year = "2001"
}