20.500.12556/DiRROS-24501 Packing $d$-dimensional balls into a $d + 1$-dimensional container In this article, we consider the problems of finding in $d + 1$ dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex body into which a given set of $d$-dimensional unit-radius balls can be packed under translations. The computational problem is neither known to be NP-hard nor to be in NP. We give a constant-factor approximation algorithm for each of these containers based on a reduction to finding a shortest Hamiltonian path in a weighted graph, which in turn models the problem of stabbing the centers of the input balls while keeping them disjoint. We also show that for $n$ such balls, a container of volume $O(n^{d−1 \over d})$ is always sufficient and sometimes necessary. As a byproduct, this implies that for $d \ge 2$ there is no finite size $(d + 1)$-dimensional convex body into which all $d$-dimensional unit-radius balls can be packed simultaneously. packings translations unit disks unit balls volume true false true Angleški jezik Ni določen Neznano 2025-12-02 14:59:07 2025-12-02 14:59:07 2025-12-03 03:42:21 0000-00-00 00:00:00 2026 0 0 13 str. article no. 102219 Vol. 132 May 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2026-05-01 004.92:514 0925-7721 10.1016/j.comgeo.2025.102219 259634179 1-s2.0-S0925772125000574-main.pdf 1-s2.0-S0925772125000574-main.pdf 1 0B37C1C4CBA562D3CE602CE909955EC7 b705bbf7b17ad57f9587dd7e7cf7d52f3b9ea90955ba487a227d3f96edbcecf9 f072c603-cf87-11f0-94a7-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=36517 https://www.sciencedirect.com/science/article/pii/S0925772125000574 1 140882ba-cf87-11f0-94a7-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=36516 Inštitut za matematiko, fiziko in mehaniko 0 0 0