points and we can return $NULL$.

It remains to show how the points can be “decoded”, i.e., how to obtain the coordinates of a point from its coordinates in the rank space of $P_j$. We also need to show how the query point $q$ can be transformed into the rank space. For each cell $C_j$ of the shallow cutting we keep the list $rlist(C_j)$ of rectangles $R_{i_1}$, $R_{i_2}$, $\ldots$, such that $list(C_j)\setminus P'$ is contained in these rectangles; for every rectangle we store the global coordinates of its endpoints. By Theorem \[theor:shallowpart\] $rlist(C_j)$ consists of $O(d^3)$ rectangles. We can identify a point $p$ in $list(C_j)\setminus P'$ by specifying the rectangle $R_{i_p}$ that contains $p$ and its $x$-rank in the rectangle $R_{i_p}$ (the $x$-rank of a point $p$ in a rectangle $R$ is the number of points in $R$ to the left of $p$). Since the list $rlist(C_j)$ consists of $O(d^3)$ rectangles, the rectangle $R_{i_p}$ can be identified by its position in $rlist$ using $O(\log d)$ bits. Each rectangle $R\in {{\cal R}}$ contains of $O(t\cdot d^4)$ points. Hence we can store the $x$-rank of $p$ in $R_{i_p}$ using $O(\log t + \log d)$ bits. Thus $p$ is represented using $O(\log t+ 