Computing Upper Bounds for the Packing Density of Congruent Copies of a Convex Body

Abstract

In this paper we prove a theorem that provides an upper bound for the density of packings of congruent copies of a given convex body in ℝⁿ; this theorem is a generalization of the linear programming bound for sphere packings. We illustrate its use by computing an upper bound for the maximum density of packings of regular pentagons in the plane. Our computational approach is numerical and uses a combination of semidefinite programming, sums of squares, and the harmonic analysis of the Euclidean motion group. We show how, with some extra work, the bounds so obtained can be made rigorous.