Partitioning a rectangle into small perimeter rectangles

DOI10.1016/0012-365X(92)90261-DMaRDI QIDQ1197044zbMATH OpenOpenAlexFDO

Authors Noga Alon, Daniel J. Kleitman

Publication date 16 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)90261-d

zbMATH Keywords

partitionperimeterrectanglessquare

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45)

Review text

The authors discuss the following question: How can one partition the unit square into \(n\) rectangles with edges parallel to the axes, so as to minimize the largest perimeter among the rectangles. They prove that the best construction for \(n=k^ 2+s\), with \(s=1\) or \(s=-1\), has \(k-1\) rows of \(k\) identical rectangles and one row of \(k+s\) identical rectangles, with all rectangles having the same perimeter. Also discussed is the analogous problem for partitioning a rectangle into \(n\) smaller rectangles.

Recommendations

• Covering a square by small perimeter rectangles
• The decomposition of a square into rectangles of minimal perimeter
• The Decomposition of a Rectangle into Rectangles of Minimal Perimeter
• Partitioning a square into rectangles: NP-Completeness and approximation algorithms
• scientific article; zbMATH DE number 4075941

Cites work

• Covering a square by small perimeter rectangles
• scientific article; zbMATH DE number 4053637 (Why is no real title available?)
• The decomposition of a square into rectangles of minimal perimeter

Cited in

(12)

• The decomposition of a square into rectangles of minimal perimeter
• Two-dimensional partitions
• Partitioning a square into rectangles: NP-Completeness and approximation algorithms
• Rectangle transformation problem
• New results for the Mondrian art problem
• scientific article; zbMATH DE number 431514 (Why is no real title available?)
• It’s Hard to Color Antirectangles
• The Decomposition of a Rectangle into Rectangles of Minimal Perimeter
• Algorithms and Computation
• On Partitions of a Rectangle into Rectangles with Restricted Number of Cross Sections
• Results in Q-measure
• An approximation algorithm for dissecting a rectangle into rectangles with specified areas

This page was built for publication: Partitioning a rectangle into small perimeter rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1197044)