Title: The Critical Packing Density of Circles

Speaker: Prof. Sándor P. Fekete, Department of Computer Science, TU Braunschweig, Germany

Time & Location: 11am - 12:20pm, Wednesday (May 1) @ NCS 120

Abstract: Consider a set of geometric objects that need to be placed into a given container, e.g., a set of circles that need to be packed into a square or circular box. Problems of this type are notoriously difficult, both in theory and practice.

In this talk I will describe results for a particularly simple criterion for deciding packability of a given set: Only consider the ratio between the total area of the items to be packed and the container. The critical density is the maximum value delta, such that any set of total area at most delta can be packed into a given container of unit area. For packing squares into a square, it was shown by Moon and Moser in 1967 that the critical packing density is 0.5.

I will show recent results on the critical density of packing circles:
- For the case of a square container, it is 0.539...
- For the case of a circular container, it is 0.5.
There are also a number of extensions for other shapes to be packed and for triangular containers.

The results are joint work with Sebastian Morr, Phillip Keldenich and Christian Scheffer.