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

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

1 Citation (Scopus)

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 ℝ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
PublisherSpringer
Pages155-188
Number of pages34
ISBN (Electronic)978-3-662-57413-3
ISBN (Print)978-3-662-57412-6
DOIs
Publication statusPublished - 2018

Publication series

NameBolyai Society Mathematical Studies
PublisherSpringer
Volume27
ISSN (Print)1217-4696

Keywords

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

Fingerprint

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