Partitioning a rectangle into small perimeter rectangles

✍ Scribed by Noga Alon; Daniel J. Kleitman

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 593 KB
• Volume: 103
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90261-d

✦ Synopsis

We show that the way to partition a unit square into kZ + s rectangles, for s = 1 or s = -1, so as to minimize the largest perimeter of the rectangles, is to have k -1 rows of k identical rectangles and one row of k + s identical rectangles, with all rectangles having the same perimeter.

We also consider the analogous problem for partitioning a rectangle into n rectangles and describe some possible approaches to it.