$C$.

In this section we show that conflict lists of all cells in a $t$-shallow cutting can be almost covered by 3-d boxes unbounded in $z$-direction. The conflict list of each cell is contained in $O(d^3)$ boxes where $d$ is a parameter that does not depend on $t$. There can be a small number of points that is not contained in these $O(d^3)$ boxes. However the total number of such points for all conflict lists is $O(|P|/d)$.

\[theor:shallowpart\] Let ${{\cal C}}$ denote a $t$-shallow cutting of a three-dimensional point set $P$, $|P|=m$. For any integer $d>0$ there exists a subset $P'$ of $P$ and a set of three-dimensional rectangles ${{\cal R}}=\{\,R_1,R_2,\ldots, R_s\,\}$, such that

(a)

:   $|P'|=O(m/d)$

(b)

:   Rectangles $R_i$ are unbounded along the $z$-axis.

(c)

:   The conflict list of any cell, except for points from $P'$, is contained in $O(d^3)$ rectangles from ${{\cal R}}$, $$list(C_i)\cap (P\setminus P')\subseteq (list(C_i)\cap R_{i_1})\cup (list(C_i)\cap R_{i_2})\cup\ldots\cup (list(C_i)\cap R_{i_g}$$ for $g=O(d^3)$.

(d)

:   Each rectangle contains $O(t\cdot d^4)$ points of $P$.

We represent $P'$ as a union of three sets $P'=P_1\cup P_2\cup P_3$. $P_1$ is the subset containing all points from $P$ that are stored in conflict lists of at least $d$ different 