[SoC Colloquium] Helmut Alt, Packing Problems: Algorithms and Complexity

Packing problems are concerned with positioning geometric objects so that they do not overlap and require an amount of space as small as possible. They have been investigated within mathematics for centuries starting with the famous Kepler conjecture. There are many surprising properties and open problems in connection with packing. The lecture will give a short survey about these “classical” issues but then concentrate on algorithms for packing. Since already the most simple variants are NP-hard, it makes sense to look for efficient approximation algorithms. We will present constant factor approximations for packing rectangles and convex polygons into containers which are minimum area rectangles or convex sets. Algorithms for analogous problems concerning three-dimensional objects will be presented, as well.
This is joint research with Mark de Berg, Christian Knauer, Léonard von Niederhäusern, and Nadja Scharf.