standard arithmetic operations can be performed on words in constant time. (In some cases our methods also make use of “non-standard” operations. However we can always implement these operations with table look-ups. The necessary look-up tables can be initialized in $O(n^{{\varepsilon}})$ time.). The space usage is measured in words of $\log n$ bits, unless specified otherwise.

First we describe the linear-space data structure for five-sided three-dimensional range reporting. We explain how the standard grid approach in Section \[sec:recur\]. We prove our result about “covering” a shallow cutting by rectangles in Section \[sec:cover\] and show how this covering can be used to obtain a compact dominance reporting data structure in Section \[sec:slabdomin\]. The same data structure can be easily modified to support two-dimensional range minima queries. Using the same approach, we obtain an $O(n\log\log n)$-space data structure for range minima and five-sided reporting queries with $O(\log \log n)$ (resp. $O((k+1)\log\log n)$ query time; this result is described in Section \[sec:minima2\]. The data structure for four-dimensional orthogonal range reporting is presented in Section \[sec:fourdim\].

Recursive Grid {#sec:recur}
==============

We divide the $(x,y)$ grid into $\sqrt{n/\log^3 n}$ vertical slabs and $\sqrt{n/\log^3n}$ horizontal slabs, so that each slab contains $\sqrt{n\log^3 n}$ points. For every 