FAST ALGORITHMS FOR 3-D DOMINANCE REPORTING AND COUNTING

摘要

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) query time using O(n(logn){sup}ε) 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){sup}2) time using O(n((logn){sup}(1+ε)))/loglogn) space.