cells for a parameter $d$. The number of points in $P_1$ is at most $O(n/d)$. Next we construct the set $P_2$ and the set of rectangles ${{\cal R}}$, so that conditions (b) and (c) are satisfied. Finally we will remove some rectangles from ${{\cal R}}$ and construct $P_3$, so that condition (d) is satisfied. For simplicity we sometimes do not distinguish between a rectangle or a point and its projection on the $xy$-plane.

#### Staircases, Regions, and Neighborhoods

Consider the corners $c_i$ of all cells $C_i$ in a shallow cutting. We can assume that no $c_i$ is dominated by another corner $c_j$ (if this is the case, $C_i$ is contained in $C_j$ and we can remove the cell $C_i$ from the shallow cutting).

Let $M$ be the set of projections of corners onto the $xy$-plane. We decompose $M$ into maximal layers (layers of maxima) $M_i$: $M_1$ is the set of maximal points[^4] of $M$. $M_2$ is the set of maximal points of $M\setminus M_1$ and $M_i$ for $i> 2$ is the set of maximal points in $M\setminus (\cup_{j=1}^{i-1} M_j)$. Thus every point on $M_i$ is dominated by some point on $M_{i-1}$ and no point on $M_i$ is dominated by another 