##
I/O-Efficient Batched Range Counting and Its Applications to Proximity
Problems

Tamás Lukovszki, Anil Maheshwari, and Norbert Zeh

####
Abstract

We present an algorithm to answer a set *Q* of range counting queries
over a point set *P* in *d*-dimensions. The algorithm takes *O*(*sort*(|*P*|+|*Q*|)
+ (|*P*|+|*Q*|)*alpha*(|*P*|)/DB log^{d-1}_{M/B}((|*P*|+|*Q*|)/B)
) I/Os and uses linear space. For an important special case the *alpha*(|*P*|)
term in the I/O-complexity of the algorithm can be eliminated. We apply
this algorithm to construct
*t*-spanners for Point sets in **R**^{d}
and polygonal obstacles in the plane, and finding the *K* closest
pairs in **R**^{d.}