cutting a cake without destroying the toppings There is a square cake. It contains N toppings - N disjoint axis-aligned rectangles. The toppings may have different widths and heights, and they do not necessarily cover the entire cake.
I want to divide the cake into 2 non-empty rectangular pieces, by either a horizontal or a vertical cut, such that the number of toppings I destroy (i.e. cross in the interior) is minimized.
What is the number of toppings I will have to destroy, in the worst case, as a function of N?
CURRENT BOUNDS:
Upper bound $N/2$:
Take any horizontal cut. If it crosses no more than N/2 toppings, then we are done. Otherwise, make a vertical cut between two of the crossed rectangles. This vertical cut does not cross any rectangle crossed by the horizontal cut, therefore it crosses at most N/2 toppings.
Lower bound $N/4$:
In the following cake, with 4 toppings, every cut must cross at least 1 topping:
aaaaaaaa bb
aaaaaaaa bb
cc ..... bb
cc ..... bb
cc ..... bb
cc dddddddd
cc dddddddd

As MvG suggested, it is possible to cut each rectangle into $N/4$ parallel strips, forcing a cut to destroy at least $⌊N/4⌋$ toppings.
NOTE: I just found out that this problem is related to the topic of Geometric separators. The lower bound example and the upper bound proofs are given in Section 4 of Smith and Wormald (1998). There is still a gap between the lower and upper bound.

Supposing the cake is open, and the toppings are open, we can position them so that a cut between edge and topping is impossible, and cuts between adjacent toppings are possible.
It appears that $\lfloor \frac{N}{4} \rfloor$ is the maximal case for a given $N>1$ on your two-dimensional cake, as demonstrated by your $N=4$ layout.  For $N=8$ put two parallel toppings where each one of yours is.  For $N=4k$ put $k$ parallel toppings.
For $N=1$ we just use a single topping covering the whole surface.
Proof that for $N=2$ or $N=3$ there is no layout requiring a cut topping is a first step to proving $\lfloor \frac{N}{4} \rfloor$ is the correct formula.
