# New Data Structures for Orthogonal Range Searching

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 *R*^{3}, 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* 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)

**BIBT**_{E}X 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"
}