**Next:** Problem 74: Slicing Axes-Parallel Rectangles

**Previous:** Problem 72: Polyhedron with Regular Pentagon Faces

- Statement
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).- Origin
Posed by R. Nandakumar, May 2009.

- Status/Conjectures
Please see below.

- Partial and Related Results
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].

- Related Open Problems
- Categories
polygons; partitioning; dissections

- Entry Revision History
R. Nandakumar, 13 May 2009; J. O’Rourke, 8 July 2009; 5 Jan. 2011.

- [EKFIR08]
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.- [Nan10b]
R. Nandakumar. Cutting mutually congruent pieces from convex regions. http://arxiv.org/abs/1012.3106, 2010.

- [Nan10a]
R. Nandakumar. ’Congruent partitions’ of polygons—a short introduction. http://arxiv.org/abs/1002.0122, 2010.