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.