TY - RPRT
T1 - Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Range Counting
Y1 - 2003
A1 - Shi,Qingmin
A1 - JaJa, Joseph F.
A1 - Mortensen,Christian
KW - Technical Report
AB - 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. ``Surpassing the information theoretic bound with fusion trees'', {\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)
PB - Instititue for Advanced Computer Studies, Univ of Maryland, College Park
VL - UMIACS-TR-2003-101
UR - http://drum.lib.umd.edu/handle/1903/1318
ER -