Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
5  
@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
3  
@BrianM.Scott I call shotgun on the top half. –  Daniel Rust Oct 1 '13 at 1:28
1  
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

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.