R|\le d^2\cdot t$, we charge no more than $1$ dollar to each point.

All rectangles associated to corners of a fixed maximal layer $M_i$ are disjoint. A planar point between the staircase of $M_i$ and the staircase of $M_{i+1}$ can be covered by at most one rectangle associated to some corner of $M_j$ for every $j$, $i-d< j\le i$. Therefore $\pi(p)$ for any point $p\in P$ is contained in at most $d$ rectangles from ${{\cal R}}$. Thus each point of $P$ is charged at most $d$ times. Hence the total cost of creating $P_3$ is $O(m\cdot d)$ dollars, where $m$ is the total number of points in $P$. Since the cost of inserting a point into $P_3$ is $d^2$, $P_3$ contains $O(m/d)$ points.

Summing up, $P'=P_1\cup P_2\cup P_3$ contains $O(m/d)$ points. For every cell $C_j$ of ${{\cal C}}$, $list(C_j)\cap (P\setminus P')$ is covered by $O(d^3)$ rectangles from ${{\cal R}}$ and every $R\in {{\cal R}}$ contains $O(t\cdot d^4)$ points of $P$.

Dominance Queries in a Slab {#sec:slabdomin}
===========================

Now we describe the compact data structure that supports capped dominance range reporting queries. By a slight misuse of notation, in this Section $P$ will denote the set of points in a slab.

