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

None, None; None, None

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

Book Chapter (2018)

Author(s)

Fernando Mário De Oliveira Filho (TU Delft - Discrete Mathematics and Optimization)

Frank Vallentin (Universität zu Köln)

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

DOI related publication

https://doi.org/10.1007/978-3-662-57413-3_7 Final published version

To reference this document use

https://resolver.tudelft.nl/uuid:24e72348-2767-4178-84ef-1584c6b23697

More Info

expand_more

Publication Year

2018

Language

English

Pages (from-to)

155-188

Publisher

Springer

ISBN (print)

978-3-662-57412-6

ISBN (electronic)

978-3-662-57413-3

Downloads counter

147

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.