2026-08-11T09:54:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13835 2024-03-06T10:52:50Z ddc:004 open_access

Packing Squares into a Disk with Optimal Worst-Case Density Fekete, Sándor P. Gurunathan, Vijaykrishna Juneja, Kushagra Keldenich, Phillip Kleist, Linda Scheffer, Christian Square packing packing density tight worst-case bound interval arithmetic approximation We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is δ = 8/(5π)≈ 0.509. This implies that any set of (not necessarily equal) squares of total area A ≤ 8/5 can always be packed into a disk with radius 1; in contrast, for any ε > 0 there are sets of squares of total area 8/5+ε that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square (1/2), circles in a square (π/(3+2√2) ≈ 0.539) and circles in a circle (1/2) have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sándor P. Fekete and Vijaykrishna Gurunathan and Kushagra Juneja and Phillip Keldenich and Linda Kleist and Christian Scheffer 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.36 urn:nbn:de:0030-drops-138356 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.36 eng https://creativecommons.org/licenses/by/4.0/legalcode