Cake Cutting Algorithms – 6 : Fair Convex Partitioning

Well,

This post is a digression in the series of posts which discussed about cake cutting algorithms, in a sense that definition of “fair” changes in this article and it introduces a new concept of convex partitioning. I acknowledge my dear friend rik for bringing this problem to my notice.

Problem : A cake is to be divided amongst n people. The condition is that each one should get a single piece, so all these pieces have to be of the same size. ( By “same size” we mean that volume of the cake has to be same. In this case, given any piece, everybody would evaluate it to posses the same value, which was not the case for earlier articles. ) Entire cake is homogeneous so if we look the cake from the top, we need to divide the cake into exactly n pieces such that area of the top view of every piece has the same area. Furthermore, the frosting would be poured onto the pieces after they have been cut, so all pieces should have equal perimeter. Looking from the top, cake is a convex set.

So, the cake ( a 2-d convex set ) has to be divided in n pieces of equal area and equal perimeter.

Solution : Well, those who are looking curiously for a solution, I am sorry to say that this problem is an open problem in general. That is, it is yet unknown whether for any given n and any given convex set such a partitioning even exist and if so, how to achieve such a partitioning. For more details one can visit this web page.

However, for n=2 the proof that a partitioning exist is very easy. The proof is based on intermediate value theorem which states that for a continuous function f if f(x_1) = 0, f(x_2)=1 then there exist a point z such that f(z) = 1/2.

Claim 1 : Given any direction, there exist a line which bisect the convex set into two parts such that they have equal area.

Proof : For any given direction, let’s have a line such that the entire convex set is below the line. Let us define a function f such that f(y)= fraction of area of the convex set above the line, where y denotes the intersection point between the line and y-axis . Now, slowly move the line downwards so that it intersects with the convex set. So, initially f(y)=0 and at the end f(y)=1. So intermediate value theorem tells us that there exist a line when f(y) = 1/2. When, the direction is parallel to y-axis we can use x-intercepts.

Claim 2 : There exist a line which divides the convex set into two pieces so that the area and the perimeter of those pieces are equal.

Proof : From Claim 1, we know that for any given direction we can have a line which bisect the set area wise. Let us define a function f such that f(\theta)=(perimeter of the piece above the line – perimeter of the piece below the line), where \theta denotes the angle the line makes with x-axis. Let us say we start with \theta=0 and end with \theta=\pi. If f(0) = a then f(\pi) = -a because line has rotated 180 degree and the pieces switch their places. Again, due to intermediate value theorem we have that there exist a \theta' such that f(\theta')=0. At this point, two pieces will have equal area as well as equal perimeter.

For this proof, I took inspiration from one of my post about necklace theorem.

–Saurabh Joshi

Advertisements

Tags: , , ,

One Response to “Cake Cutting Algorithms – 6 : Fair Convex Partitioning”

  1. Seyed Mohammad Sanaei Says:

    Dear Saurabh,
    I am looking for proof of a theorem which says that equal partitioning is best when we are to decide the optimum values of independent variables of a convex function.
    can you help me?
    thank you

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: