$O(m/d)$.

Proofs of Lemma \[lemma:cov1\] and Lemma \[lemma:p2\] can be found in Section \[sec:coverlemmas\].

#### Constructing the set $P_3$.

In the final step, we exclude rectangles that contain too many points from $P$ from the set ${{\cal R}}$. Let $list({{\cal C}})=\cup_{C_j\in {{\cal C}}}list(C_j)$ denote all points from $P$ contained in the cells of ${{\cal C}}$. For any rectangle $R\in{{\cal R}}$, $|R\cap list({{\cal C}})|\le t\cdot d^2$: a rectangle $R$ is a subset of the non-empty region associated to some corner $c_j$. Hence every rectangle intersects projections of at most $d^2$ different cells. Therefore $R\cap list({{\cal C}})\le t\cdot d^2$ for all $R\in {{\cal R}}$.

If $|R\cap P|\ge t\cdot d^4$ for some rectangle $R\in {{\cal R}}$, we add all points of $R\cap list({{\cal C}})$ to $P_3$ and remove the rectangle $R$ from ${{\cal R}}$. We can show that $|P_3|=O(m/d)$: Similar to Lemma \[lemma:p2\], we assign $d$ dollars to each point of $P$ and assume that the cost of inserting a point into $P_3$ is $d^2$ dollars. If points from $R\cap list({{\cal C}})$ are added to $P_3$, then we charge the cost to $P\cap R$. The cost is evenly distributed among all points of $P\cap R$. Since $|P\cap R|\ge d^4\cdot t$ and $|list({{\cal C}})\cap 