New Data Structures for Orthogonal Range Searching

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

In Proc. 41st Annual Symposium on Foundations of Computer Science, pages 198-207, 2000.

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).

Copyright notice

Copyright © 2000 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Online version

focs00.pdf (173 Kb)

DOI

10.1109/SFCS.2000.892088

BIBTEX entry

@inproceedings{focs00,
  author = "Stephen Alstrup and Gerth St{\o}lting Brodal and Theis Rauhe",
  booktitle = "Proc. 41st Annual Symposium on Foundations of Computer Science",
  doi = "10.1109/SFCS.2000.892088",
  isbn = "0-7695-0850-2",
  pages = "198-207",
  title = "New Data Structures for Orthogonal Range Searching",
  year = "2000"
}

Other versions