3
$\begingroup$

I got interested in a cake cutting problem from computational perspective. Suppose we have a piece of cake and we want to slice it into pieces using several cuts (straight lines). 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 cake pieces equals to $|M|*|N|$.

A parallel pair is a set of two cuts that do no cross each other. Crossings (intersection points) of cuts are NOT allowed on the circle boundary. All intersection points are inside the circle. So, two cuts must cross inside the circle. Finally, any crossing point is the result of the intersection of exactly two cuts (lines).

Joseph's answer provides an efficient algorithm to find the maximum number of pieces. The complexity of the following problem remains open:

Given integer $K$, Is there an efficient algorithm to decide the existence of a set of $N$ non-parallel cuts that result in $K$ pieces of cake (no pair of cuts is parallel) or is it NP-complete?

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ OK. What about K-1 many concurrent lines, with common point far away from the circle, and all of them intersecting the circle non trivially (non tangentially)? Gerhard "What Does Parallel Really Mean?" Paseman, 2016.12.10. $\endgroup$
    – Gerhard Paseman
    Commented Dec 11, 2016 at 7:26
  • 1
    $\begingroup$ If a parallel pair's "extensions outside the circle on both ends do not cross," doesn't that imply that they are simply parallel lines clipped to the disk? $\endgroup$
    – Joseph O'Rourke
    Commented Dec 11, 2016 at 12:40
  • 1
    $\begingroup$ Unfortunately, that restriction does not reduce the triviality. I can take my concurrent solution and tweak the lines so that all points of intersection lie outside the circle, resulting in K pieces. To a casual observer the portion inside the circle will look unchanged. If you insist that all intersection points are strictly inside, you get what Joseph provided in his post. Tweaking a solution to allow more than two lines concurrent inside the circle allows you fewer regions. I don't think you've captured a good problem yet. Gerhard "Is Reading Between The Lines" Paseman, 2016.12.11. $\endgroup$
    – Gerhard Paseman
    Commented Dec 11, 2016 at 16:32
  • 1
    $\begingroup$ One problem that I hoped you would mention is to find the minimum number of cuts to produce K pieces. I know of no polytime (in log K) algorithm to answer that. (Actually, one just occurred to me after I hit 'send'.) Gerhard "Don't Ask For Three Pieces" Paseman, 2016.12.11. $\endgroup$
    – Gerhard Paseman
    Commented Dec 11, 2016 at 18:06
  • 1
    $\begingroup$ I think I am misunderstanding your intent, or you are not communicating it. I ask you if you can get 5 pieces under your present scheme (with all intersection points of cuts inside the circle). I maintain that you will always get 7 with three such cuts, as you are asking every two cuts to intersect uniquely on the cake. The problem I asked (given K the number of pieces, find the minimal number of cuts) is not much better or harder, but feels more like a complexity problem than this latest version. Gerhard "Perhaps I Am Missing Something" Paseman, 2016.12.12. $\endgroup$
    – Gerhard Paseman
    Commented Dec 12, 2016 at 20:10

1 Answer 1

Reset to default
4
$\begingroup$

The maximum number of pieces has been studied under the name the lazy caterer's sequence, A000124. You have an arrangement of $n$ lines in general position, which has at most $n(n+1)/2+1$ cells, over which you lay your circle.

The figure below is from the Wikipedia article.

            LazyCat

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your answer and the beautiful figure. Are you aware of the complexity of the above problems for the arrangement of $n$ lines? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Dec 12, 2016 at 16:50
  • $\begingroup$ @MohammadAl-Turkistany: Doesn't feel NP-hard to me. Judicious placement of the circle to capture exactly $K$ cells. Sorry, I don't see a clear algorithm at the moment... $\endgroup$
    – Joseph O'Rourke
    Commented Dec 12, 2016 at 19:19
  • $\begingroup$ One can imagine a chord of the unit circle passing within $r \lt 1/2$ of the center. One can (for small $r$) rotate the circle by an angle of $k\pi/n$ radians to place up to $n$ chords, each which intersect each other, and no point is on three or more lines. This will give the maximum (and indeed only, given all n choose 2 points of intersection are within the unit circle) number of pieces for $n$ cuts. I am still struggling to see a good problem coming from this thread. Gerhard "No Matter How I Turn" Paseman, 2016.12.12. $\endgroup$
    – Gerhard Paseman
    Commented Dec 12, 2016 at 21:32

You must log in to answer this question.

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