Problem 67: Fair Partitioning of Convex Polygons

Statement

Define a fair partitioning of a polygon as a partition of it into a finite number of pieces so that every piece has both the same area and the same perimeter. If all the resulting pieces are convex, call it a fair convex partitioning. Given any positive integer n, can any convex polygon be convex fair partitioned into n pieces?

If the answer is ``Not always,'' how does one decide the possibility of such a partitioning for a given polygon and a given n? And if a fair convex partition exists for a specific polygon, how does one find a fair partitioning that minimizes the total length of the cut segments, or minimizes the sum of the perimeters of the pieces?

And finally, what could one say about higher dimensional analogs of this question?

Origin

Posed by R. Nandakumar and N. Ramana Rao, June 2007.

Status/Conjectures

Open. The originators tend to believe every convex polygon allows a fair convex partition into n pieces for any n. There have been recent advances in 2010: Aronov and Hubard [AH10], and independently Karasev [Kar10], have established the conjecture for any prime power, n = p^k.

Partial and Related Results

See [NR08] for an introduction and survey and proof that the conjecture holds for n = 2, and a proof for n = 4. This survey cites a new result of Barany, Blagojevic, and Szucs [forthcoming] that establishes the conjecture for n = 3. The cited survey also sketches a (different) argument for n = 3.

There is work on partitioning convex polygons into equal area convex pieces so that every piece equally shares the boundary of the given target polygon: [ANRCU98] [AKK+98].

A proof of a weaker result--that any polygon allows fair partitioning for any n (where the pieces need not be convex) is proposed at http://nandacumar.blogspot.com/2006/10/cutting-shapes-ii.html.

Categories

polygons; partitioning

Entry Revision History

R. Nandakumar and N. Ramana Rao, 14 Jul 2007, 17 Sep 2007; J. O'Rourke, 1 Jan 2009; 23 Jan. 2009; 30 Dec. 2010.

Bibliography

AH10

Boris Aronov and Alfredo Hubard.
Convex equipartitions of volume and surface area.
http://arxiv.org/abs/1010.4611, October 2010.

AKK+98

Jin Akiyama, A. Kaneko, M. Kano, Gisaku Nakamura, Eduardo Rivera-Campo, S. Tokunaga, and Jorge Urrutia.
Radial perfect partitions of convex sets in the plane.
In Japan Conf. Discrete Comput. Geom., pages 1-13, 1998.

ANRCU98

Jin Akiyama, Gisaku Nakamura, Eduardo Rivera-Campo, and Jorge Urrutia.
Perfect divisions of a cake.
In Proc. Canad. Conf. Comput. Geom., pages 114-115, 1998.

Kar10

Roman N. Karasev.
Equipartition of several measures.
http://arxiv.org/abs/1011.4762v2, November 2010.

NR08

R. Nandakumar and N. Ramana Rao.
'Fair' partitions of polygons--an introduction.
http://arxiv.org/abs/0812.2241, 2008.