Next: Problem 74: Slicing Axes-Parallel Rectangles
Previous: Problem 72: Polyhedron with Regular Pentagon Faces
Partition a given polygon P into n mutually congruent pieces so that the area of P not covered by the union of the pieces is as small as possible. A partition which leaves out the least area is an optimal congruent partition for that n. If a congruent partition is a perfect cover, leaving no area uncovered, then it is called a perfect congruent partition. Two polygons are congruent if one can be made to coincide with the other by translation, rotation, or reflection (flipping over).
Posed by R. Nandakumar, May 2009.
Please see below.
A new introduction to the problem is now available: [Nan10a].
It is known that there exist quadrilaterals with no perfect congruent partition for any n: http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/December2003.html.
Deciding whether P has a perfect congruent partition appears little explored for n>2. The case of n=2 is solved in [EKFIR08] with an O(n^3) algorithm.
If congruence is restricted to translation and rotation only, to what extent does the problem change?
Can the left-over area be upper-bounded as a function of P and n? An attempt for n=2 is offered in [Nan10b].
polygons; partitioning; dissections
R. Nandakumar, 13 May 2009; J. O’Rourke, 8 July 2009; 5 Jan. 2011.
Dania El-Khechen, Thomas Fevens, John Iacono, and Günter Rote. Partitioning a polygon into two mirror congruent pieces. In Proc. 20th Canad. Conf. Comput. Geom., pages 131–134, August 2008.
R. Nandakumar. Cutting mutually congruent pieces from convex regions. http://arxiv.org/abs/1012.3106, 2010.
R. Nandakumar. ’Congruent partitions’ of polygons—a short introduction. http://arxiv.org/abs/1002.0122, 2010.