I/O-efficient batched range counting and its applications to proximity problems
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 (Formula Presented) I/Os and uses linear space. For an important special case, the α(|P|) term in the I/Ocomplexity of the algorithm can be eliminated. We apply this algorithm to constructing t-spanners for point sets in ℝd and polygonal obstacles in the plane, and finding the K closest pairs of a point set in ℝd.
Lukovszk, T. (Tamás), Maheshwari, A, & Zeh, N. (Norbert). (2001). I/O-efficient batched range counting and its applications to proximity problems.