# Cache-Oblivious Planar Orthogonal Range Searching and Counting

In * Proc. 21st Annual ACM Symposium on Computational Geometry*, pages 160-169, 2005.

## Abstract

We present the first cache-oblivious data structure for planar
orthogonal range counting, and improve on previous results for
cache-oblivious planar orthogonal range searching.

Our range counting structure uses *O*(*N*log_{2} *N*) space and answers
queries using *O*(log_{B} *N*) memory transfers, where *B* is the
block size of any memory level in a multilevel memory hierarchy.
Using bit manipulation techniques, the space can be further
reduced to *O*(*N*). The structure can also be modified to support
more general semigroup range sum queries in *O*(log_{B} *N*) memory
transfers, using *O*(*N*log_{2} *N*) space for three-sided queries and
*O*(*N*log_{2}^{2} *N*/log_{2}log_{2} *N*) space for four-sided queries.

Based on the *O*(*N*log *N*) space range counting structure, we develop
a data structure that uses *O*(*N*log_{2} *N*) space and answers
three-sided range queries in *O*(log_{B} *N*+*T*/*B*) memory transfers,
where *T* is the number of reported points. Based on this structure,
we present a general four-sided range searching structure that uses
*O*(*N*log_{2}^{2} *N*/log_{2}log_{2} *N*) space and answers queries in
*O*(log_{B} *N* + *T*/*B*) memory transfers.

**Copyright notice**
Copyright © 2005 by the Association for Computer Machinery, Inc.

**Online version**

socg05.pdf (210 Kb)

**DOI**

10.1145/1064092.1064119

**BIBT**_{E}X entry

@inproceedings{socg05,
author = "Lars Arge and Gerth St{\o}lting Brodal and Rolf Fagerberg and Morten Laustsen",
booktitle = "Proc. 21st Annual ACM Symposium on Computational Geometry",
doi = "10.1145/1064092.1064119",
isbn = "1-58113-991-8",
pages = "160-169",
title = "Cache-Oblivious Planar Orthogonal Range Searching and Counting",
year = "2005"
}