Packing and covering by translates of certain nonconvex bodies

Abstract:

We develop techniques for determining the packing and covering constants for star bodies composed of cubes. In the theory of convex sets problems of tiling, packing, and covering by translates of a given set have a long history, with the main focus on the packing and covering by spheres. Only in a few cases is the densest packing or sparsest covering known, even in the case of the sphere, except, of course, when the set happens to tile Euclidean space. In a series of papers S. K. Stein [4], [5], [6], [7] and W. Hamaker [1] used algebraic techniques in the problem of tiling Euclidean space of arbitrary dimension by translates of certain star bodies composed of cubes. The present paper has two purposes. First, it establishes a “Shift Theorem” that reduces tiling, packing, and covering problems for translates of a union of cubes to translates by vectors with integer coordinates. In a sense, this reduces continuous geometric problems in Euclidean space to discrete algebraic problems in a power of the infinite cyclic group. This theorem automatically generalizes many of Stein’s results that depend on the assumption of integer translates. Second, it illustrates the Shift Theorem and a general “contribution” argument by determining the packing and covering constants for a particular star body.