Kolloquium: Effizientes Packen geometrischer Objekte

Am 23. Mai 2014 referiert Prof. Dr. Helmut Alt, Professor an der Freien Universität Berlin, zum Thema. Der Vortrag startet um 12:30 Uhr in Hörsaal 5.

Zum Vortrag:

Das effiziente Packen einer vorgegebenen Menge geometrischer Objekte hat auch im zweidimensionalen Raum wichtige Anwendungen - etwa in der Metall- oder der Textilindustrie. Es ergeben sich eine Vielzahl an Varianten, je nachdem

• welcher Art die Objekte sind, also: Polygone, konvexe Polygone oder Rechtecke

• oder welcher Art die zum Packen zulässigen Bewegungen sind, also: Verschiebungen (Translationen) oder zusätzlich Drehungen (starre Bewegungen)

Es gibt zahlreiche heuristische Verfahren für solche Probleme. Doch auch für scheinbar einfache Spezialfälle ist kein effizienter Algorithmus zu ihrer exakten Lösung bekannt. Es ist leicht zu zeigen, dass selbst das optimale Packen einer Menge achsenparalleler Rechtecke unter Translationen bereits NP-vollständig ist. Dies beweist, dass schon das zu den schwierigsten praktischen Problemen gehört.

Naheliegend ist die Frage, ob es effiziente Algorithmen gibt, die diese Probleme zwar nicht optimal, doch annähernd lösen. Für die Praxis reicht dies meistens schon aus.

Der Vortrag gibt eine Einführung in die Problematik und die Komplexität der Probleme sowie eine Übersicht über die Techniken, mit denen bereits Spezialfälle gelöst werden konnten.

Zum Referenten:

Der Referent Prof. Dr. Helmut Alt hat die Forschungsgruppe Theoretische Informatik an der FU Berlin aufgebaut. Sie unterhält inzwischen ein dichtes Netzwerk mit Wissenschaftlern auf der gesamten Welt, mit denen ein reger personeller Austausch und akademische Zusammenarbeit unternommen wird. Die algorithmische Geometrie ist ein Forschungsschwerpunkt dieser Gruppe. Sie  bietet exzellente Möglichkeiten für eine Promotion im Anschluss an ein Master-Studium. Prof. Sebastian Iwanowski hält engen Kontakt zu den Wissenschaftlern der Gruppe, da er selbst in dieser Forschungsgruppe promoviert hat.

In Kürze:

Was: Kolloquium - Effizientes Packen geometrischer Objekte
Wann: 23.05.2014, 12:30
Wo: Hörsaal 5