@article {15026,
	title = {Space-efficient and fast algorithms for multidimensional dominance reporting and counting},
	journal = {Algorithms and Computation},
	year = {2005},
	month = {2005///},
	pages = {1755 - 1756},
	abstract = {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. ldquoSurpassing the information theoretic bound with fusion treesrdquo, Journal of Computer and System Sciences, 47:424{\textendash}436, 1993], our algorithms achieve O(log n/loglog n+f) query time for the 3-dimensional dominance reporting problem, where f is the output size, and O(log n/loglog n) query time for the 2-dimensional dominance counting problem. We extend these results to any constant dimension d ge 3, achieving O(n(log n/loglog n)d {\textendash} 3) space and O((log n/loglog n)d {\textendash} 2+ f) query time for the reporting case and O(n(log n/loglog n)d {\textendash} 2) space and O((log n/loglog n)d {\textendash} 1) query time for the counting case.},
	doi = {10.1007/978-3-540-30551-4_49},
	author = {JaJa, Joseph F. and Mortensen,C. and Shi,Q.}
}
