Computing upper bounds for the packing density of congruent copies of a convex body
Preprint
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 $\mathbb{R}^n$; 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.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- New Upper Bounds for the Density of Translative Packings of Three-Dimensional Convex Bodies with Tetrahedral SymmetryDiscrete & Computational Geometry, 2017
- The Local Optimality of the Double Lattice PackingDiscrete & Computational Geometry, 2016
- The Packing Density of the $n$ n -Dimensional Cross-PolytopeDiscrete & Computational Geometry, 2015
- Upper Bound on the Packing Density of Regular Tetrahedra and OctahedraDiscrete & Computational Geometry, 2010
- Dense Crystalline Dimer Packings of Regular TetrahedraDiscrete & Computational Geometry, 2010
- Lower Bounds for Measurable Chromatic NumbersGeometric and Functional Analysis, 2009
- Research Problems in Discrete Geometry2005
- Double-lattice packings of convex bodies in the planeDiscrete & Computational Geometry, 1990
- Real zeros of positive semidefinite forms. IMathematische Zeitschrift, 1980
- Spherical codes and designsGeometriae Dedicata, 1977