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 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?
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.