FAST ALGORITHMS FOR 3-D DOMINANCE REPORTING AND COUNTING
Qingmin Shi, Joseph F. JáJá · International Journal of Foundations of Computer Science · 2004
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( log n/ log log n+f) 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(( log n/ log log n)2) time using O(n log1+∊n/ log log n) space.