Simon Tippenhauer

Algorithmen zum effizienten Packen und Stapeln von geometrischen Objekten

Betreuer: Prof. Dr. Helmut Alt
Abgabedatum: 01.11.2012

Kurzbeschreibung

In der vorliegenden Arbeit werden Algorithmen zum effizienten Packen und Stapeln von geometrischen Objekten untersucht und entwickelt. Beim Packen von Objekten soll eine möglichst kompakte Anordnung gefunden werden, sodass alle Objekte disjunkt sind. Im Gegensatz dazu dürfen die Objekte beim Stapeln auch ineinander platziert werden.

Der Schwerpunkt der Arbeit basiert auf den aktuellen Ergebnissen von Arkin et al. für das Stapeln einer Menge von konvexen Polygonen. Sie haben gezeigt, wie die Polygone in polynomieller Zeit so angeordnet werden können, dass der Umfang der konvexen Hülle eine (1+ epsilon)–Approximation bezüglich der konvexen Hülle einer optimalen Anordnung ist.

Darauf aufbauend konnte ein Verfahren für das effiziente Stapeln von dreidimensionalen Polytopen zur Optimierung des Durchmessers der konvexen Hülle entwickelt werden.