Take the 2-minute tour ×

Any bounded convex set of the Euclidean plane can be cut into two convex pieces of equal area and circumference.

Can one cut every bounded convex set of the Euclidean plane into an arbitrary number $n$ of convex pieces having equal area and circumference?

The solution of this problem for $n=2$ is generically unique. Are there other values of $n$ (assuming that the problem is possible) where this happens?

More generally, given a $d-$dimensional bounded convex set $C$ in the Euclidean space $\mathbf E^d$ of dimension $d$. for which values of $n$ can one cut $C$ into $n$ convex pieces of equal area with boundaries of equal $(d-1)-$dimensional area? ($n=2$ is again easy, but the solution is no longer generically unique if $d>2$). Are there values for $(n,d)$ for which the solution always exists in a generically unique way (or for which the number of solutions is generically finite)?

share|improve this question
Try looking in Jiri Matousek, Using the Borsuk-Ulam theorem, because it mentions similar problems. I don't think it talks about convex sets, but instead cutting arbitrary shapes to equal pieces with straight lines. Expect to find lots of hard and unsolved questions. –  Zsbán Ambrus May 12 '10 at 9:45
It's "fair partition problem". May be this site would be helpful - garden.irmacs.sfu.ca/?q=op/… –  Nurdin Takenov May 12 '10 at 9:58
Thanks, especially to Takenov for the link, mentionning exactly the same problem. After reflection, I am convinced that the answer must always be yes by a dimension argument (for $n=3$, you can choose an arbitrary interior point $P$ together with a ray starting at $P$ thus determining uniquely two other rays cutting the convex set into $3$ pieces of equal area. We have moreover to satisfy two identities coming from the equal perimeter requirement and we have three degrees of liberty. The solution should thus exist and should not be unique.) –  Roland Bacher May 12 '10 at 10:24
I added the open-problem tag as this is a well known open problem. –  domotorp May 12 '10 at 10:34
add comment

3 Answers

Permit me (as a late-comer) to add a bit more information. The 2D version of your question was posed by R. Nandakumar and N. Ramana Rao and posted at TOPP. They have written "an introduction" to their "Fair Partitioning" problem: http://arxiv.org/abs/0812.2241. They cite a forthcoming paper by Barany, Blagojevic, and Szucs that settles the problem (positively) for $n=3$.

Addendum (3Dec10): A significant advance on this problem was just announced by Boirs Aronov and Alfredo Hubard , the latter of whom is giving a seminar talk on this at NYU. They solved it (positively) for all prime powers $n$. Here is the abstract of the talk, entitled "From the sandwich to the waist":

I will talk about a Ham Sandwich/Borsuk Ulam type theorem. Let $K$ be a convex body, for any prime power $n=p^k$ it is possible to partition $K$ into $n$ convex pieces with equal areas and equal perimeter.

This confirms a conjecture of Nandakumar and Ramana Rao (for all prime powers). The proof uses some basic ideas from optimal transport and from equivariant topology. It turns out that this is closely related to one of the main ingredients of the proof by Gromov of the Waist of the Sphere inequality.

Here is a paper on Gromov's "waist of the sphere" theorem.

Edit. Here is an arxiv paper by Aronov & Hubard on their work.

share|improve this answer
My understanding is that Aronov, Hubard, and Karasev are in communication with one another. –  Joseph O'Rourke Dec 3 '10 at 20:02
A related question: Is it possible to efficiently compute these partitions, or is it just an existence result? Seems like it will be hard to compute these partitions---but can one exploit the proof structure to approximately compute these partitions? –  Suvrit Dec 4 '10 at 2:11
add comment

I feel that the question is somehow "wrong" even though it is perfectly reasonable. So let me answer a strongly related, more or less known, but not quite the same question.

Say, $P \subset \Bbb R^2$ is a bounded convex set with the boundary $\partial P$. Question: can one cut $P$ into $n$ convex parts with $n-1$ straight cuts, such that each part has equal area and equal portion of the boundary $\partial P$ (think of dividing the cake fairly with respect to the size and the frosting). I claim that this is possible with straight cuts. The difference with your problem is that somehow I ignore the internal part of the perimeter.

Rather than give you a complete proof I will simply tell you that this is an easy corollary of the "inscribed chord theorem" and the "fair division" applications I give. You can read it up in my book, subsections 4.3 and 4.4. I know it's a bad trick to refer to your own writings, but this is the best ref I know. Alternatively, you can read the first part of the story in these terrific lecture notes by Hopf. Note also that the original lemma (due to P. Lévy) has a second part which in this case suggests that any other division (like say 30% and 70%) is not going to work in some cases (I haven't thought this through though).

Now, here is a final thought: if you don't insist on convexity, you can always manipulate the diagonal cuts to make them longer curves in such a way that all parts will be non-convex but have equal perimeter. Perhaps this will help.

share|improve this answer
Thanks for this reply. I think I can see the proof. By the way, I do not agree that your question is more natural, except when dealing with cakes. The framework of the initial question is completely natural when considering fields enclosed by fences. –  Roland Bacher May 12 '10 at 10:38
@Roland-bacher: Except that you only have to build one fence on the interior cutting lines - so that these are only weighted half - which actually is important in the more than 2 pieces problem. A better example and more closely related to the "frosting case" may be the "dipping case", where you dip your particular piece (of something) in the dip after it is cut. –  Thomas Kragh May 12 '10 at 14:32
I agree with you. –  Roland Bacher May 19 '10 at 16:54
add comment

There is a generalization of this question, where "area" and "circumference" are replaced by arbitrary "nice" measures (for the purpose of this answer, say absolutely continuous measures) $\mu$ and $\nu$ on $\mathbb{R}^2$. Bárány and Matoušek have a nice paper on the subject.

Even more generally, fix nice probability measures $\mu_1,\ldots,\mu_i$ on $\mathbb{R}^2$. A $k$-fan in $\mathbb{R}^2$ consists of $k$ rays (semi-infinite lines) $r_1,\ldots,r_k$ emanating from a point, listed in some clockwise order. (In fact $k$-fans are also allowed to emanate from the point at infinity, i.e., a set of $k$ parallel lines is considered to be a $k$-fan.) Write $C_k$ for the region proceeding $r_k$ in the clockwise order.

Given a vector $\alpha=(\alpha_1,\ldots,\alpha_k)$ with non-negative entries summing to one, say that $\mu_1,\ldots,\mu_r$ can be simultaneously $\alpha$-partitioned if there exists a $k$-fan such that $\mu_i(C_j)=\alpha_j$ for each $i=1,\ldots,r$ and $j=1,\ldots,k$. (If $\alpha_1=\ldots=\alpha_k=1/k$ say that the measures can be simultaneously equipartitioned. This case, with $k=2$, is closest to the original )

Bárány and Matoušek have a whole host of results about when such partitions exist and do not exist. Here are just a couple:

  • For any $k \geq 5$ and any $\alpha$, there are two measures that can not be simultaneously $\alpha$-partitioned.
  • For any $\alpha=(\alpha_1,\alpha_2)$, any two measures can be simultaneously $\alpha$-partitioned, even if the center of the fan is specified in advance.

No one knows, for example, if any two measures can be simultaneously equipartitioned into four parts. Karasev seems to have a paper where he proves that any two measures can be simultaneously equipartitioned into $q$ convex parts, whenever the number of parts is a prime power. (This was first achieved for three parts -- this is the result by Bárány et al that Joseph O'Rourke mentioned.) I am unclear on the relation between this and the result of Hubard and Aronov, mentioned by Joseph O'Rourke in his answer.

Higher-dimensional versions have also been considered but much is open. For example, for any three measures in $\mathbb{R}^3$ can one always find a convex $3$-partition of space so that each measure has measure $1/3$ on each part? (I heard Bárány say in a seminar that the version with $3$ replaced by a power of $2$, is known to be true; but I didn't note down a reference.)

share|improve this answer
add comment

Your Answer


