2026-07-24T01:59:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10467 2024-03-06T10:46:03Z ddc:004 open_access

Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition) Becker, Aaron T. Fekete, Sándor P. Keldenich, Phillip Morr, Sebastian Scheffer, Christian Packing complexity bounds packing density We motivate and visualize problems and methods for packing a set of objects into a given container, in particular a set of {different-size} circles or squares into a square or circular container. Questions of this type have attracted a considerable amount of attention and are known to be notoriously hard. We focus on a particularly simple criterion for deciding whether a set can be packed: comparing the total area A of all objects to the area C of the container. The critical packing density delta^* is the largest value A/C for which any set of area A can be packed into a container of area C. We describe algorithms that establish the critical density of squares in a square (delta^*=0.5), of circles in a square (delta^*=0.5390 ...), regular octagons in a square (delta^*=0.5685 ...), and circles in a circle (delta^*=0.5). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aaron T. Becker and Sándor P. Fekete and Phillip Keldenich and Sebastian Morr and Christian Scheffer 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.63 urn:nbn:de:0030-drops-104678 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.63 eng https://creativecommons.org/licenses/by/3.0/legalcode