\log d)=O(\log \log n)$ bits. Hence every rectangle $R\in {{\cal R}}$ contains a poly-logarithmic number of points from the global set of points.

Every rectangle $R\in {{\cal R}}$ is unbounded along the $z$-axis. Hence we can retrieve the point coordinates by answering a special kind of two-dimensional queries, further called *capped range selection* queries. A capped range selection query $(Q,v)$ for a two-dimensional rectangle $Q=[a,b]\times [c,d]$ and an integer $v\le \log^{10} n$ returns the point with $x$-rank $v$ in the rectangle $Q$, i.e., the $v$-th leftmost point in $Q$. Let $P_{glob}$ denote the global set of points. Slabs are created by dividing the structure on previous recursion level along the $x$- or $y$-axis. Therefore $P_{glob}\cap R= P\cap R$ for every $R\in {{\cal R}}$. Hence we need only one instance of the capped range selection data structure for all recursive slabs.

Capped range selection can be viewed as a generalization of the range successor problem [@NN12] and can be solved using compact range trees and some auxiliary data structures. We will show in Section \[sec:smallsel\] that capped selection queries can be answered in $O(\log^{{\varepsilon}}n)$ time using an $O(n)$ space data structure. However, we have to decompose each rectangle from ${{\cal R}}$ 