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\left( {sort(\left| P \right| + \left| Q \right|) + \tfrac{{(\left| P \right| + \left| Q \right|)\alpha (\left| P \right|)}}
{{DB}}\log _{M/B}^{d - 1} \tfrac{{\left| P \right| + \left| Q \right|}}
{B}} \right)^1
$
O\left( {sort(\left| P \right| + \left| Q \right|) + \tfrac{{(\left| P \right| + \left| Q \right|)\alpha (\left| P \right|)}}
{{DB}}\log _{M/B}^{d - 1} \tfrac{{\left| P \right| + \left| Q \right|}}
{B}} \right)^1
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.
Research supported by NSERC, NCE GEOIDE, and DFG-SFB376.
sort(N) denotes the I/O-complexity of sorting N data items in external memory. See Model of Computation.