Seminar

 
 
Abstract
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, Leonard von Niederhaeusern, and Nadja Scharf.
 
Speaker biography
Helmut Alt got his doctorate at Universitaet des Saarlandes, Germany in 1976. He taught for six years at the Pennsylvania State University, U.S.A., for one year at University of Hildesheim, Germany, and for 31 years at Freie Universitaet Berlin, Germany. His research has been concerned with
algorithms and complexity theory, in particular complexity of arithmetics and computational geometry. In the latter field he mostly concentrated on the recognition and analysis of geometric shapes.