Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting

摘要

We present linear-space sub-logarithmic algorithms for handling the 3-dimensional dominance reporting and the 2-dimensional dominance counting problems. Under the RAM model as described in [M. L. Fredman and D. E. Willard. "Surpassing the information theoretic bound with fusion trees", Journal of Computer and System Sciences, 47:424-436, 1993], our algorithms achieve O(log n/ log log n + f) query time for the 3-dimensional dominance reporting problem, where f is the output size, and O (log n/ log log n) query time for the 2-dimensional dominance counting problem. We extend these results to any constant dimension d ≥ 3, achieving O(n(log n/ log log n)~(d-3)) space and O((log n/ log log n)~(d-2) + f) query time for the reporting case and O(n(log n/ log log n)~(d-2)) space and O((log n/ log log n)~(d-1)) query time for the counting case.