Section \[sec:figures\]. The set of rectangles ${{\cal R}}$ consists of all rectangles associated to corners of ${{\cal C}}$.

The *neighborhood* of a corner $c_j$ is defined as follows. We shoot a horizontal ray in $-x$ direction until we either (i) hit the boundary of an empty region or (ii) cross the boundaries of $d$ non-empty regions or (iii) hit the staircase of $M_{i+d}$. We also shoot a vertical ray in $-y$ direction until we either (i) hit the boundary of an empty region or (ii) cross the boundaries of $d$ non-empty regions or (iii) hit the staircase of $M_{i+d}$. We call all rectangles whose boundaries are crossed by the vertical and the horizontal rays from $c_j$ the *neighbors* of $c_j$.

There are at most $O(d^3)$ rectangles associated to neighbors of a corner $c_j$.

Each corner has at most $2d$ neighbor regions. Every region is divided into $O(d^2)$ rectangles.

\[lemma:cov1\] For any point $p$ in $list(C_j)$, either $p\in P_1\cup P_2$ or $p$ is contained in some rectangle $R_{j_f}$ associated to a neighbor of $c_j$.

We can bound the number of points in conflict lists of corners with empty regions.

\[lemma:p2\] The number of points in a set $P_2$ is bounded by 