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  logd-1M/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 Rd and polygonal obstacles in the plane, and finding the K closest pairs in Rd.