Return to Question

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 non-parallel cuts that result in $K$ pieces of cake (no pair of cuts is parallel) or is it NP-complete?

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?

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 of cuts are NOT allowed on the circle boundary. All intersection points are inside the circle. So, two cuts must cross either inside the circle but they can not cross each other on the circle boundary. Finally, any crossing point is the result of the intersection of exactly two cuts (line).

I there an efficient algorithm to find the number of pieces in general (each cut can take any direction)? Also, 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 is parallel) or is it NP-complete?

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 non-parallel cuts that result in $K$ pieces of cake (no pair of cuts is parallel) or is it NP-complete?

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

I there an efficient algorithm to find the number of pieces in general (each cut can take any direction)? Also, 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 is parallel) or is it NP-complete?

Definition: A parallel pair is a set of two cuts that do no cross each other (also their extensions outside the circle on both ends do not cross). Crossings of cuts are NOT allowed on the circle boundary. So, two cuts must cross either inside or outside the circle but they can not cross each other on the circle boundary.

To eliminate all trivial cases (some raised by Gerhard), any crossing point (inside or outside the circle) is the result of the intersection of exactly two cuts.

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 of cuts are NOT allowed on the circle boundary. All intersection points are inside the circle. So, two cuts must cross either inside the circle but they can not cross each other on the circle boundary. Finally, any crossing point is the result of the intersection of exactly two cuts (line).

I there an efficient algorithm to find the number of pieces in general (each cut can take any direction)? Also, 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 is parallel) or is it NP-complete?