into $O(\log^{1+{\varepsilon}} n)$ parts. Therefore we need $O(\log^{2+{\varepsilon}} n)$ additional bits per rectangle. A detailed description is provided in Lemma \[lemma:smallsel\] in Section \[sec:smallsel\].

Using Lemma \[lemma:smallsel\], we can retrieve the coordinates of any point $p$ in $C_j$ in $O(\log^{{\varepsilon}} n)$ time: we know the rectangle $R\in {{\cal R}}$ that contains $p$ and we know the $x$-rank $\ell$ of $p$ in $R$. Hence we can return the global coordinates of $p$ in $O(\log^{{\varepsilon}} n)$ time by answering a query $(R,\ell)$. If we can retrieve a point from cell $C$ in time $O(\log^{{\varepsilon}} n)$, we can also reduce the query $q$ to the rank space of $C$ within the same time; see Section \[sec:rankspace\].

The conflict lists of all cells contain $O(m)$ points. Data structures for all cells of the shallow cutting use $O(m\log\log n)$ bits. For each cell we also store the list of rectangles and spend $O(\log^{2+{\varepsilon}} n)$ bits per rectangle (for the capped selection data structure). In total we need $O(d^3\log^{2+{\varepsilon}} n)=o(t)$ bits for every cell and $O(m)$ bits for all cells. The data structure for the subset $P'$ uses $O((m/\log n)\log n)=O(m)$ bits. To identify a cell of the shallow cutting that contains the query point, we 