Densest Lattice Packings of 3-Polytopes

For a given convex body the lattice packing problem is the task to find a lattice of minimal determinant such that two different lattice translates of the body have no interior points in common. The ratio of the volume of the body to the determinant of such an optimal lattice is called the density of a densest lattice packing and it can be interpreted as the maximal proportion of the space that can be occupied by non-overlapping lattice translates of the body. It was already shown by Minkowski that the lattice packing problem is equivalent to the problem of determining a so called critical lattice of the difference body of the given convex body, where a lattice is called a critical lattice of a 0-symmetric convex body if it has minimal determinant among all lattices for which the origin is the only lattice point contained in the interior of the body. The difference body is just the Minkowski sum of the body and its image reflected in the origin. For more information on packings we refer to [2].

The lattice packing problem for a general convex body in n-dimensional space is very hard. In fact, for dimensions not less than 3 the only exact results are on space fillers (for which the density is one) and on the unit sphere. For the unit sphere the problem is solved in dimensions not greater than 8 - since 1934! (see [4]).

In contrast for planar bodies there are several techniques to solve the problem and there exists also an algorithm for polygons, due to Mount and Silverman. However already in 3-space the situation is rather more complicated. Apart from the 3-dimensional space fillers and from cylinders based on a convex disk, for which the problem is equivalent to the determination of the lattice packing density of the convex disk, densest lattice packings are only known for the tetrahedron, cubeoctahedron, a family of truncated cubes, a double cone and for the frustrums of a sphere. It is worth to mention that the family of frustrums of a sphere includes the 3-sphere as a limiting case, for which the packing density was determined already by Gauss.

The computations of the densities of the bodies mentioned above may be regarded as an application of a general method developed by Minkowski [3] which characterizes densest packing lattices of a 3-dimensional convex body by certain properties. However this method was considered as rather impractical (see [4]). In [1] Minkowski's work is used as a starting point for the construction of an efficient algorithm to compute the lattice packing density of an arbitrary 3-polytope. As a demonstration of the efficiency of the algorithm optimal lattice packings of the Platonic and Archimedean polytopes are calculated. The precise values of the densities (expressed as algebraic numbers) as well as coordinates of optimal lattices for these bodies can be found in [1]. Here we just give rounded floating point numbers.

We recall briefly the definition of the Platonic and Archimedean solids. The five Platonic solids (mentioned in Plato's Timaios) are the only 3-dimensional convex regular poytopes, i.e., all facets are regular and congruent and all vertex figures are congruent. A polytope is called semi-regular if all facets are regular (but not necessarily congruent) and all vertex figures are congruent. Beside the Platonic solids and an infinite series of prisms and antiprisms there are exactly thirteen semi-regular convex polytopes in 3-space, the so called Archimedean solids. These solids were described by Archimedes, and most of them (except the snub dodecahedron) were rediscovered during the Renaissance. A first systematic study and enumeration of the Archimedean polytopes is due to Kepler in 1619.


  1. Ulrich Betke and Martin Henk: Densest Lattice Packings of 3-Polytopes, Comp. Geom. 16 (3), 157 - 186, (2000).
  2. Peter Michael Gruber and Cornelius Gerrit Lekkerkerker: Geometry of Numbers , North-Holland, Amsterdam (1987).
  3. Hermann Minkowski: Dichteste gitterförmige Lagerung kongruenter Körper , Nachr. K. Ges. Wiss. Göttingen, Math.-Phys. KL (1904), 311 - 355; (see also Gesammelte Abhandlungen vol. II, 3 - 42, Leipzig 1911).
  4. Claude Ambros Rogers: Packing and Covering , Cambridge University Press, Cambridge (1964).