  In this paper we study the four-dimensional dominance range reporting problem
and present data structures with linear or almost-linear space usage. Our
results can be also used to answer four-dimensional queries that are bounded on
five sides. The first data structure presented in this paper uses linear space
and answers queries in $O(\log^{1+\varepsilon}n + k\log^{\varepsilon} n)$ time,
where $k$ is the number of reported points, $n$ is the number of points in the
data structure, and $\varepsilon$ is an arbitrarily small positive constant.
Our second data structure uses $O(n \log^{\varepsilon} n)$ space and answers
queries in $O(\log n+k)$ time.
  These are the first data structures for this problem that use linear (resp.
$O(n\log^{\varepsilon} n)$) space and answer queries in poly-logarithmic time.
For comparison the fastest previously known linear-space or
$O(n\log^{\varepsilon} n)$-space data structure supports queries in
$O(n^{\varepsilon} + k)$ time (Bentley and Mauer, 1980). Our results can be
generalized to $d\ge 4$ dimensions. For example, we can answer $d$-dimensional
dominance range reporting queries in $O(\log\log n (\log n/\log\log n)^{d-3} +
k)$ time using $O(n\log^{d-4+\varepsilon}n)$ space. Compared to the fastest
previously known result (Chan, 2013), our data structure reduces the space
usage by $O(\log n)$ without increasing the query time.
