Packing 2D disks into a 3D container
share
In this article, we consider the problem of finding in three dimensions a minimum-volume axis-parallel box into which a given set of unit-radius disks can be packed under translations. The problem is neither known to be NP-hard nor to be in NP. We give a constant-factor approximation algorithm based on reduction to finding a shortest Hamiltonian path in a weighted graph. As a byproduct, we can show that there is no finite size container into which all unit disks can be packed simultaneously.
READ FULL TEXT