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

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

2 Answers 2

up vote 1 down vote accepted

The lower bound $r=\lfloor \frac N4\rfloor$ is also an upper bound:

Assume that in a square with toppings one must cut at least $r>1$ toppings with every cut. Number the edges of the square with $E_1,E_2,E_3,E_4$ clockwise, and set $\varepsilon_i=min\{d(E_i,R_j)\ :\ d(E_i,R_j)>0\}$, where $R_j$ is any of the edges of a rectangle of the toppings which is parallel to $E_i$. Note that $\varepsilon_i$ can be the distance of a rectangle to the edge $E_i$ or the width of that rectangle (and in that case the rectangle has an edge in $E_i$). Choose one of the rectangles which define $\varepsilon_i$ and name it $R_i$.

Set $T_i$ to be the line parallel to $E_i$ at a distance $\varepsilon_i$. By our assumption, $T_i$ must cut at least $r$ rectangles, denote the set of these rectangles with $S_i$. Note that, by the minimality of $\varepsilon_i$, all rectangles in $S_i$ have an edge contained in $E_i$.

Clearly $R_i\notin S_i$, and it is also easy to check that $R_i\notin S_{i+2}$, the subindices taken $i\mod 4$, since then there would be a cut along a side of $R_i$ which cuts at most 1 topping. We also have $S_1\cap S_3=\emptyset$, since a rectangle $R$ in $S_1\cap S_3$ allows us to cut through the middle of $R$, parallel to $E_2$, cutting through only one rectangle (topping). Similarly $S_2\cap S_4=\emptyset$. Now we assume that for a given number $r$ (of minimal number of toppings destroyed by a cut) the number $N$ of rectangles is minimal. We can assume that in this configuration we can choose the rectangles $R_i$ to have an edge contained in $E_i$. In fact, if no rectangle with an edge in $T_i$ touches $E_i$, then we can extend one of the rectangles with distance $\varepsilon_i$ so that it touches $E_i$. The new configuration has the same number of rectangles, and the number of toppings destroyed by each cut is either equal or has increased by one.

Let $r_1$ be the new minimal number of toppings destroyed by a cut, and so $r_1\ge r$. Note that eventually the $\varepsilon_i$ have changed. But now for each edge $E_i$ there are $r_1+1$ rectangles with an edge contained in $E_i$, the $r_1$ rectangles in (the new) $S_1$ and the rectangle $R_i$. None of these rectangles can have two edges contained in opposite edges $E_i,E_{i+2}$, and there can be at most one rectangle with a corner in $E_i,E_{i+1}$. Hence there are at least $|S_1|+|S_2|+|S_3|+|S_4|+4-4$ distinct rectangles. We arrive at $$ N\ge |S_1|+|S_2|+|S_3|+|S_4|\ge 4r_1\ge 4r\quad\Rightarrow \quad 4r\le N \quad\Rightarrow \quad r\le \left\lfloor \frac N4\right\rfloor. $$

share|improve this answer
    
By $\epsilon_i$, do you mean the smallest distance from an edge $E_i$ of the cake to a parallel edge of a topping? But what if all epsilons are 0? –  Erel Segal-Halevi May 26 at 4:36
    
If a rectangle has an edge in $E_i$, then the distance of the opposite edge to $E_i$ is positive. –  san May 27 at 0:45
    
But you defined $\epsilon_i$ as minimum, i.e. the smallest distance from $E_i$ to any parallel edge. This smallest distance might be 0 for all $i$. –  Erel Segal-Halevi May 27 at 5:42
    
I defined $\varepsilon_i$ to be the smallest of the positive distances. –  san May 27 at 11:28
    
Ah, I see, I mis-read. –  Erel Segal-Halevi May 27 at 12:10

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 '14 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.