Q. Shi and J.F. JaJa (USA)
algorithms, structures, orthogonal range query
We present in this paper fast algorithms for the 3-D dominance reporting and counting problems, and generalize the results to the d-dimensional case. Our 3-D dominance reporting algorithm achieves O(logn/loglogn + f)(1) query time using O(n log^ε n) space , where f is the number of points satisfying the query and ε > 0 is an arbitrarily small constant. For the 3-D dominance counting problem (which is equivalent to the 3-D range counting problem), our algorithm runs in O((logn/loglogn)^2) time using O(nlog^1+ε n/loglogn) space.
Important Links:
Go Back
