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. No published work specifically on this problem is known.

Partial and Related Results

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.

Bibliography

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.