because a dominance data structure consumes $O(\log\log n)$ bits per point and each point is kept in two slabs. Hence $S(n)= O(n\log\log n) +2\sqrt{n/\log^3 n}S(\sqrt{n \log^3 n})$. We set $c(n)=S(n)/n$ and divide both parts of the previous equality by $n$. Thus $c(n)=O(\log\log n) + 2c(\sqrt{n\log^3 n})$. The latter recursion can be resolved to $c(n)=O(\log n)$. Hence $S(n)=O(n\log n)$ and the data structure uses $O(n)$ words of $\log n$ bits.

\[lemma:capped5side\] There exists a data structure that uses $O(n)$ words of space and supports five-sided queries in $O((k+1)\log^{{\varepsilon}}n)$ time.

Covering of a Shallow Cutting {#sec:cover}
=============================

Our main tool in designing a compact dominance data structure is shallow cuttings. A $t$-shallow cutting for a set $P$ is a collection of $O(n/t)$ cells such that each cell $C$ is a rectangle of the form $[0,a]\times [0,b]\times [0,c]$. Furthermore each cell contains at most $2t$ points from $P$ and every point $q$ in 3-d space that dominates at most $t$ points from $P$ is contained in some cell(s). The list of all points from $P$ in a cell $C$ is called a conflict list of $C$ and denoted $list(C)$. For a cell $C=[0,a]\times [0,b]\times [0,c]$, the point $(a,b,c)$ is called the corner of 