Packing $d$-dimensional balls into a $d + 1$-dimensional containerAlt, Helmut (Avtor) Cabello, Sergio (Avtor) Cheong, Otfried (Avtor) Park, Ji-won (Avtor) Seiferth, Nadja (Avtor) packingstranslationsunit disksunit ballsvolumeIn 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.20262025-12-02 14:59:05Članek v reviji176508sl