15
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ are all toppings identical in dimension? $\endgroup$
    – mau
    Commented Sep 30, 2013 at 12:54
  • $\begingroup$ @mau given the cake is square, and not cubical, I think we can assume we're working in dimension 2 here. $\endgroup$
    – Dan Rust
    Commented Sep 30, 2013 at 13:04
  • 5
    $\begingroup$ @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! :-) $\endgroup$ Commented Oct 1, 2013 at 1:21
  • 4
    $\begingroup$ @BrianM.Scott I call shotgun on the top half. $\endgroup$
    – Dan Rust
    Commented Oct 1, 2013 at 1:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – MvG
    Commented Oct 1, 2013 at 22:43

2 Answers 2

2
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$ Commented May 26, 2015 at 4:36
  • $\begingroup$ If a rectangle has an edge in $E_i$, then the distance of the opposite edge to $E_i$ is positive. $\endgroup$
    – san
    Commented May 27, 2015 at 0:45
  • $\begingroup$ 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$. $\endgroup$ Commented May 27, 2015 at 5:42
  • 1
    $\begingroup$ I defined $\varepsilon_i$ to be the smallest of the positive distances. $\endgroup$
    – san
    Commented May 27, 2015 at 11:28
  • $\begingroup$ Ah, I see, I mis-read. $\endgroup$ Commented May 27, 2015 at 12:10
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$? $\endgroup$ Commented Jan 10, 2014 at 11:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .