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

Research output: Chapter in Book/Conference proceedings/Edited volumeChapterScientific

3 Citations (Scopus)


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 ℝ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.

Original languageEnglish
Title of host publicationNew Trends in Intuitive Geometry
EditorsG. Ambrus, I. Bárány , K.J. Böröczky, G.F. Tóth, J. Pach
Place of PublicationBerlin
Number of pages34
ISBN (Electronic)978-3-662-57413-3
ISBN (Print)978-3-662-57412-6
Publication statusPublished - 2018

Publication series

NameBolyai Society Mathematical Studies
ISSN (Print)1217-4696


  • Delsarte’s method
  • Euclidean motion group
  • Lovász theta number
  • Pentagon packings
  • Polynomial optimization
  • Semidefinite programming
  • Sphere packings
  • Tetrahedra packings


Dive into the research topics of 'Computing Upper Bounds for the Packing Density of Congruent Copies of a Convex Body'. Together they form a unique fingerprint.

Cite this