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

-
are all toppings identical in dimension? –  mau Sep 30 '13 at 12:54
@mau given the cake is square, and not cubical, I think we can assume we're working in dimension 2 here. –  Daniel Rust Sep 30 '13 at 13:04
@Daniel: Otherwise we can cut it parallel to the top and bottom of the cake, halfway down, and even get two equal pieces without destroying any toppings! :-) –  Brian M. Scott Oct 1 '13 at 1:21
@BrianM.Scott I call shotgun on the top half. –  Daniel Rust Oct 1 '13 at 1:28
You could take your last example and cut each rectangle into $\frac N4$ parallel strips, forcing a cut to destroy at least $\left\lfloor\frac N4\right\rfloor$ toppings. So far I couldn't come up with a better solution, but that doesn't poove that there is none. –  MvG Oct 1 '13 at 22:43

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.
How can you prove that $k$ is actually the worst case for all $N=4k$? Maybe there is an arrangement of $4k$ toppings in which you will have to destroy more than $k$? –  Erel Segal Halevi Jan 10 at 11:14