Packings ofR^nby certain error spheres
Sherman K. Stein · IEEE Transactions on Information Theory · 1984
Golomb in 1969 defined error metrics for codes and their corresponding "error spheres." Among the error spheres are the cross and semicross. The cross is defined as follows. Letkandnbe positive integers. The(k, n)-cross in Euclideann-spaceR^{n}consists of2kn + 1unit cubes: a central cube together with2narms of lengthk. The(k, n)-semicross inR^{n}consists ofkn + 1unit cubes: a comer cube together withnarms of lengthkattached atnof its nonopposite faces. For instance, the(1, 2)-cross has five squares arranged in a cross and the(1, 2)-semicross is shaped like the letterL. Much has been done on determining when translates of a cross or semicross tile (or tesselate)R^{n}. If translates do not tile, we may ask how densely they can pack space without overlapping. We answer this question for the(k, n)-cross in all dimensions and forklarge. We also show that packings by the cross that are extremely regular (lattice packings) do just about as well as arbitrary packings by the cross. However, for the semicross, even inR^{3}, when the arm lengthkis large, lattice packings are much less dense than arbitrary packings. The methods are primarily algebraic, involving Abelian groups.