Problem 73: Congruent Partitions of Polygons

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

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

2. 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³) algorithm.

3. If congruence is restricted to translation and rotation only, to what extent does the problem change?

4. Can the left-over area be upper-bounded as a function of P and n?

Related Open Problems

Problem 67

Categories

polygons; partitioning; dissections

Entry Revision History

R. Nandakumar, 13 May 2009; J. O'Rourke, 8 July 2009.

Bibliography

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.