Next: Problem 74: Slicing AxesParallel
Up: The Open Problems Project
Previous: Problem 72: Polyhedron with
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
 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 leftover area be upperbounded as a function of P and n?
An attempt
for n = 2 is offered in [Nan10b].
 Related Open Problems
 Problem 67
 Categories
 polygons; partitioning; dissections
 Entry Revision History
 R. Nandakumar, 13 May 2009; J. O'Rourke, 8 July 2009; 5 Jan. 2011.
 EKFIR08

Dania ElKhechen, Thomas Fevens, John Iacono, and Günter Rote.
Partitioning a polygon into two mirror congruent pieces.
In Proc. 20th Canad. Conf. Comput. Geom., pages 131134,
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 polygonsa short introduction.
http://arxiv.org/abs/1002.0122, 2010.
Next: Problem 74: Slicing AxesParallel
Up: The Open Problems Project
Previous: Problem 72: Polyhedron with
The Open Problems Project  December 04, 2015