In cake-cutting, we cut a round cake into $m$ pieces by $n$ cuts. If we seek maximum $m$ pieces with $n$ cuts, we may observe that the area unbalance increases greatly with $m$. Could we define a mathematical relationship among the unbalance, pieces and cuts?

Let's describe it precisely in math notions. Given a unit disk with total area $\pi$, for a configuration $c$ of $n$ straight lines, $c$ cuts the disk into $m$ pieces, and the area of each piece is $A_i$.

Define the portion of each piece by $p_i = \frac{A_i}{\pi}$

The area unbalance may be described by entropy: $$S_2 = - \sum_{i=1}^{m}p_i \ln p_i$$

The arc length of the outer pieces is also unbalanced, a similar entropy $S_1$ can be introduced:

$$S_1 = - \sum_jq_j \ln q_j$$

where $q_j = \frac{L_j}{2 \pi}$ is the portion of the segments of the circumference.

Could we describe the relationship among $S_1$, $S_2$, $m$ and $n$? And given $m$ and $n$, which cut $c$ leads to the least unbalance $S_1$ and $S_2$?


1 Answer 1


This is only a partial answer but too long for a comment

$n$ lines divide the plane into at most $m = \frac{n(n+1)}{2}+1$ pieces, which is known as the lazy caterer's sequence. This results in $\frac{n(n-1)}{2}$ intersections of two lines each, or equivalently $n-1$ intersections on every line. Notice that for odd $n$ the regular $\{n/\frac{n-1}{2}\}$ star polygons satisfy these criteria:

$n$ lines have $2n$ degrees of freedom which can be represented by the $x$ and $y$ coordinates of each point of the star. Now, depending on $r := \sqrt{x^2+y^2} < 1$ we can easily compute $A_i$ and $L_j$ because of the rotational symmetry and minimize the entropies.

I don't know if this results in the optimal arangement but it is a systematic approach.


You must log in to answer this question.

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