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

Book chapter (2018)

Authors

F.M. de Oliveira Filho Discrete Mathematics and Optimization -

Research Group

Discrete Mathematics and Optimization () (TU Delft)

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

To reference this document use:

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

More Info

expand_more

Published Date

2018

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.

Files

DeOliveiraFilho_Vallentin2018_... (pdf)

(pdf | 0.616 Mb)

Unknown license

Download not available