Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 03, 2015, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Helmut Alt (FU Berlin)
Efficiently packing geometric objects is a natural question with many applications, e.g., in transportation, apparel, or steel industries. Packing of regular objects, like disks , higher dimensional spheres or axis-parallel rectangles has been considered intensely in pure mathematics as well as in operations research. Since even the most simple variants of the problem are NP-hard, efficient constant factor approximations are interesting.
In the lecture, we will consider more irregular objects, namely, convex polygons in the plane. We investigate the problem of finding a minimum-area container for packing a set of convex polygons by translations. In particular, we consider axis-parallel rectangles or arbitrary convex sets as containers. For both optimization problems we develop efficient constant factor approximation algorithms.
Joint work with Mark de Berg and Christian Knauer.
Automatic MiSe System Software Version 1.4803M | admin login