Description
Abstract: 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. We give a constant-factor approximation algorithm for each of these containers. We also show that for n such balls, a container of volume O(n^{1−1/d}) is always sufficient and sometimes necessary.
Joint work with Helmut Alt, Otfried Cheong, Ji-won Park and Nadja Seiferth.