%0 Report
%D 2003
%T An O(n)-Space O(log n/log log n + f)-Query Time Algorithm for 3-D Dominance Reporting
%A Shi,Qingmin
%A JaJa, Joseph F.
%K Technical Report
%X We present a linear-space algorithm for handling the {\emthree-dimensional dominance reporting problem}: given a set $S$ of $n$ three-dimensional points, design a data structure for $S$ so that the points in $S$ which dominate a given query point can be reported quickly. Under the variation of the RAM model introduced by Fredman and Willard~\cite{Fredman94}, our algorithm achieves $O(\log n/\log\log n+f)$ query time, where $f$ is the number of points reported. Extensions to higher dimensions are also reported. (UMIACS-TR-2003-77)
%I Instititue for Advanced Computer Studies, Univ of Maryland, College Park
%V UMIACS-TR-2003-77
%8 2003/08/01/
%G eng
%U http://drum.lib.umd.edu/handle/1903/1301