@article {15027,
	title = {Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Range Counting},
	volume = {UMIACS-TR-2003-101},
	year = {2003},
	month = {2003/11/25/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We present linear-space sublogarithmic algorithms for handling the {\emthree-dimensional dominance reporting problem} and the {\em
two-dimensional range counting problem}. Under the RAM model as described
in~[M.~L. Fredman and D.~E. Willard. {\textquoteleft}{\textquoteleft}Surpassing the information
theoretic bound with fusion trees{\textquoteright}{\textquoteright}, {\em Journal of Computer and System
Sciences}, 47:424--436, 1993], our algorithms achieve $O(\log n/\log\log
n+f)$ query time for 3-D dominance reporting, where $f$ is the number of
points reported, and $O(\log n/\log\log n)$ query time for 2-D range
counting case. We extend these results to any constant dimension $d$
achieving $O(n(\log n/\log\log n)^{d-3})$-space and $O((\log n/\log\log
)^{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.
(UMIACS-TR-2003-101)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1318},
	author = {Shi,Qingmin and JaJa, Joseph F. and Mortensen,Christian}
}
