Hostname: page-component-7b7567c8c-2rsb6 Total loading time: 0 Render date: 2026-11-12T09:56:37.630Z Has data issue: false hasContentIssue false
  • English
  • Français

Packing a rectangle with m x (m + 1) rectangles

Published online by Cambridge University Press:  14 March 2016

Richard Ellard and
Des MacHale
Richard Ellard
Affiliation:
School of Mathematical Sciences, University College Dublin, Ireland e-mail: richardellard@gmail.com
Des MacHale
Affiliation:
School of Mathematical Sciences, University College Cork, Ireland e-mail: d.machale@ucc.ie

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider the packing of rectangles of dimension m x (m + 1) — where m is a natural number — into a larger rectangle. More specifically, we consider the following problem: What is the smallest area of a rectangle into which rectangles of dimensions 1 x 2, 2 x 3, 3 x 4,…, n x (n + 1) will fit without overlap?

Unlike the corresponding problem for squares of areas 12, 22, 32, …, n2(see [1]), where there is no known non-trivial example of an exact fit into a rectangle, in many cases we can achieve an exact fit for our set of m x (m + 1) rectangles. Intuitively, this is because each m x (m + 1) rectangle has two possible orientations, which considerably increases the chances of an exact fit. As in [1], we make the (possibly unnecessary) assumption that the sides of each m x (m + 1) rectangle are parallel to the sides of the bounding rectangle, whose dimensions are integral. For any given n, we consider two solutions to our problem to be distinct only if the bounding rectangles have different dimensions (but equal area).

Information

Type
Research Article
Information
The Mathematical Gazette , Volume 100 , Issue 547 , March 2016, pp. 34 - 47
Copyright
Copyright © Mathematical Association 2016 

References

1.Ellard, Richard and MacHale, Des, Packing squares into rectangles, Math. Gaz. 96 (March 2012) pp. 1–18.Google Scholar
2.Korf, Richard E., Moffitt, Michael D., and Pollack, Martha E., Optimal rectangle packing, Annals of Operations Research, 179(1) (2010) pp. 261–295.CrossRefGoogle Scholar
3.Huang, E. and Korf, R. E., Optimal rectangle packing: an absolute placement approach, Journal of Artificial Intelligence Research, 46 (2013) pp. 47–87.CrossRefGoogle Scholar
4.Korf, Richard E., Optimal rectangle packing: new results, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS04), Whistler, British Columbia (June 2004) pp. 142–149.Google Scholar
5.Anglin, W. S., The square pyramid puzzle, The American Mathematical Monthly, 97(2) (February 1990) pp. 120–124.CrossRefGoogle Scholar
6.Stein, W. A., et∼al, Sage Mathematics Software, The Sage Development Team, accessed October 2015 at http://www.sagemath.orgGoogle Scholar