Convex 'Fair' Partitions Of Convex Polygons

Importance: Medium ✭✭
Subject: Geometry
Recomm. for undergrads: yes
Posted by: Nandakumar
on: December 12th, 2007

\textbf{Basic Question:} Given any positive integer \emph{n}, can any convex polygon be partitioned into \emph{n} convex pieces so that all pieces have the same area and same perimeter?

\textbf{Definitions:} Define a \emph{Fair Partition} 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. Further, if all the resulting pieces are convex, call it a \emph{Convex Fair Partition}.

\textbf{Questions:} 1. (Rephrasing the above 'basic' question) Given any positive integer \emph{n}, can any convex polygon be convex fair partitioned into n pieces?

2. If the answer to the above is \emph{"Not always''}, how does one decide the possibility of such a partition for a given convex polygon and a given \emph{n}? And if fair convex partition is allowed by a specific convex polygon for a give \emph{n}, how does one find the \emph{optimal} convex fair partition that \emph{minimizes} the total length of the cut segments?

3. Finally, what could one say about \emph{higher dimensional analogs} of this question?

\textbf{Conjecture:} The authors tend to believe that the answer to the above 'basic' question is "yes". In other words they guess: \emph{Every} convex polygon allows a convex fair partition into \emph{n} pieces for any \emph{n}

1. The above conjecture is easily seen to hold for \emph{n}=2. for \emph{n}=3 and above, it is not clear.

2. The \emph{n} = 2 case \emph{does not} appear to allow a recursive generalization for values of \emph{n} equal to powers of 2.

3. It can be shown that any polygon (not necessarily convex) allows a fair partitioning into \emph{n} pieces for any \emph{n}, provided the pieces need not be convex (this is not a \emph{convex} fair partition). See (4) in references below.

4. It appears that the fair parition of a convex polygon which minimizes the total length of cuts (or equivalently, the sum of the perimeters of the pieces) \emph{need not} be a convex fair partition.

5. There is no known work in this specific area. The problem of partitioning convex polygons into equal area convex pieces so that every piece \emph {equally shares the boundary} of the input polygon has been studied (references below)

Bibliography

(*)1. The original 'mainstream' statement of this problem: \href[http://maven.smith.edu/~orourke/TOPP/P67.html#Problem.67]{http://maven.smith.edu/~orourke/TOPP/P67.html#Problem.67}

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

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

4. This blog maintained by the authors has tentative thoughts, examples, etc on 'Fair Partitions': \href[http://nandacumar.blogspot.com]{http://nandacumar.blogspot.com}


* indicates original appearance(s) of problem.