next up previous
Next: Problem 74: Slicing Axes-Parallel 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].

  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(n3) 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? 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.

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.

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.


next up previous
Next: Problem 74: Slicing Axes-Parallel Up: The Open Problems Project Previous: Problem 72: Polyhedron with
The Open Problems Project - December 04, 2015