slab we keep a data structure supporting three-dimensional dominance queries, that will be described in Section \[sec:slabdomin\]. This data structure uses $O(\log\log n)$ bits per point and answers queries in $O((k+1)\log^{{\varepsilon}} n)$ time. The top data structure $D^t$ contains the $\log^{1+{\varepsilon}} n$ points with smallest $z$-coordinates from every cell. Last, we store a recursively defined data structure for every slab that contains $\Omega(\log^8 n)$ points. When the number of points in a slab does not exceed $O(\log^8 n)$, we keep all points in a data structure that uses $O(\log \log n)$ bits per point and supports queries in $O(1+k)$ time. This data structure can be constructed using standard techniques; see Section \[sec:rankspace\].

We observe that an $O(n)$-word data structure supporting five-sided queries in $O(\log^{1+{\varepsilon}}n+k\log^{{\varepsilon}}n)$ time is already known [@Chazelle88]. In Sections \[sec:recur\] - \[sec:slabdomin\] we describe the data structure for *$\log n$-capped* queries: we report all $k$ points in the query range if $k\le \log n$; if $k> \log n$, we return $NULL$. In the latter case, we can use the “slow” data structure of Chazelle and report all points in the query range in time $O(\log^{1+{\varepsilon}}n+k\log^{{\varepsilon}}n)=O((1+k)\log^{{\varepsilon}}n)$

A four-sided query (i.e., a 3-d query bounded on four sides) can be 