Cutting convex sets - MathOverflow

Cutting convex sets

2010-05-12T09:03:12Z

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)?

Answer by Igor Pak for Cutting convex sets

2010-05-12T10:18:48Z

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.

Answer by Joseph O'Rourke for Cutting convex sets

2010-05-28T17:58:03Z

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.

Answer by Louigi Addario-Berry for Cutting convex sets

2010-12-03T17:31:29Z

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