20.500.12556/RUL-176508 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 Članek v reviji 2025-12-02 14:59:05 2025-12-02 14:59:10 2026-06-30 13:26:35 0000-00-00 00:00:00 2026 0 0 13 str. art. 102219 Vol. 132 May 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 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 23975CFE79F17A3FDDE60942B996A119 0d35a5337f442baf489d482424c144761238ca8ddb72aeac0fe87443a7a8a447 7f2d126c-cf87-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=222885 https://www.sciencedirect.com/science/article/pii/S0925772125000574 1 b28808a5-cf86-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=222884 Fakulteta za matematiko in fiziko 0 0 0