Skip to main content
1 of 9

Simple cake cutting puzzle

I am got interested in a cake cutting problem from computational perspective. Suppose we have a piece of cake and we want to slice into pieces using several cuts. Each cut represents a chord on a circle. Integer multiplication is a special case were the cuts are dividable into two parallel sets $M$ and $N$ such that the number of regular cake pieces equal to $|M|*|N|$.

I there an efficient algorithm to find the number of pieces in general (each cut can take any direction)? Given integer $K$, Is there an efficient algorithm to decide the existence of a set of non-parallel cuts that result in $K$ pieces of cake (no pair of cuts are parallel) or is it NP-complete?