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

Fernando Mário De Oliveira Filho; Frank Vallentin

doi:10.1007/978-3-662-57413-3_7

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

Fernando Mário De Oliveira Filho, Frank Vallentin

Discrete Mathematics and Optimization

Research output: Chapter in Book/Conference proceedings/Edited volume › Chapter › Scientific

3 Citations (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 ℝⁿ; 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 language	English
Title of host publication	New Trends in Intuitive Geometry
Editors	G. Ambrus, I. Bárány , K.J. Böröczky, G.F. Tóth, J. Pach
Place of Publication	Berlin
Publisher	Springer
Pages	155-188
Number of pages	34
ISBN (Electronic)	978-3-662-57413-3
ISBN (Print)	978-3-662-57412-6
DOIs	https://doi.org/10.1007/978-3-662-57413-3_7
Publication status	Published - 2018

Publication series

Name	Bolyai Society Mathematical Studies
Publisher	Springer
Volume	27
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

Access to Document

10.1007/978-3-662-57413-3_7

Cite this

@inbook{24e723482767417884ef1584c6b23697,

title = "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 ℝ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 = "Delsarte{\textquoteright}s method, Euclidean motion group, Lov{\'a}sz theta number, Pentagon packings, Polynomial optimization, Semidefinite programming, Sphere packings, Tetrahedra packings",

author = "{De Oliveira Filho}, {Fernando M{\'a}rio} and Frank Vallentin",

year = "2018",

doi = "10.1007/978-3-662-57413-3_7",

language = "English",

isbn = "978-3-662-57412-6",

series = "Bolyai Society Mathematical Studies",

publisher = "Springer",

pages = "155--188",

editor = "G. Ambrus and {B{\'a}r{\'a}ny }, I. and K.J. B{\"o}r{\"o}czky and G.F. T{\'o}th and J. Pach",

booktitle = "New Trends in Intuitive Geometry",

}

Computing Upper Bounds for the Packing Density of Congruent Copies of a Convex Body. / De Oliveira Filho, Fernando Mário; Vallentin, Frank.
New Trends in Intuitive Geometry. ed. / G. Ambrus; I. Bárány ; K.J. Böröczky; G.F. Tóth; J. Pach. Berlin: Springer, 2018. p. 155-188 (Bolyai Society Mathematical Studies; Vol. 27).

Research output: Chapter in Book/Conference proceedings/Edited volume › Chapter › Scientific

TY - CHAP

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

AU - De Oliveira Filho, Fernando Mário

AU - Vallentin, Frank

PY - 2018

Y1 - 2018

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

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

KW - Delsarte’s method

KW - Euclidean motion group

KW - Lovász theta number

KW - Pentagon packings

KW - Polynomial optimization

KW - Semidefinite programming

KW - Sphere packings

KW - Tetrahedra packings

UR - http://www.scopus.com/inward/record.url?scp=85056305168&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-57413-3_7

DO - 10.1007/978-3-662-57413-3_7

M3 - Chapter

AN - SCOPUS:85056305168

SN - 978-3-662-57412-6

T3 - Bolyai Society Mathematical Studies

SP - 155

EP - 188

BT - New Trends in Intuitive Geometry

A2 - Ambrus, G.

A2 - Bárány , I.

A2 - Böröczky, K.J.

A2 - Tóth, G.F.

A2 - Pach, J.

PB - Springer

CY - Berlin

ER -

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

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Cite this