Covering a square with consecutive squares

Janos Balogh (), Gyorgy Dosa (), Lars Magnus Hvattum (), Tomas Attila Olaj (), Istvan Szalkai () and Zsolt Tuza ()
Additional contact information
Janos Balogh: University of Szeged
Gyorgy Dosa: University of Pannonia
Lars Magnus Hvattum: Molde University College
Tomas Attila Olaj: University of Pannonia
Istvan Szalkai: University of Pannonia
Zsolt Tuza: University of Pannonia

Annals of Operations Research, 2025, vol. 350, issue 3, No 1, 926 pages

Abstract: Abstract In this article we address the following problem. Given are a $$1\times 1$$ 1 × 1 square, a $$2\times 2$$ 2 × 2 square, and so on, finally a $$n\times n$$ n × n square. What is the biggest square that can be covered completely by this given set of “small” squares? It is assumed that the small squares must stand parallel to the sides of the big square, and overlap is allowed. In contrast to the packing version of the problem (asking for the smallest square that can accommodate all small squares without overlap) which has been studied in several papers since the 1960’s, the covering version of the problem seems new. We construct optimal coverings for small values of n. For moderately bigger n values we solve the problem optimally by a commercial mathematical programming solver, and for even bigger n values we give a heuristic algorithm that can find near optimal solutions. We also provide an expansion-algorithm, that from a given good cover using consecutive squares up to size n, can generate a cover for a larger square using small squares up to size $$n+1$$ n + 1 . Finally we prove that a simple covering policy can generate an asymptotically optimal covering.

Keywords: Square packing; Square covering; Asymptotic behavior; Heuristic method consecutive squares; Board packing (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-025-06633-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:350:y:2025:i:3:d:10.1007_s10479-025-06633-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-025-06633-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().