Yussuf Kassem

Approximation von Kreispackungen

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 15.02.2016

Kurzbeschreibung

Ich habe mich mit der Approximation einer minimalen rechteckigen Packung für Kreise beliebiger Größe beschäftigt. 

Die Approximation basiert auf einen Algorithmus von Prof. Helmut Alt, Prof. Mark de Berg und Prof. Christian Knauer, welcher für die Approximation von rechteckigen minimalen Packungen konvexer Polygone entwickelt wurde. Das Ergebnis der Anwendung auf Kreise ist ein Approximationsfaktor von 9,049 in linearer Laufzeit. Der besagte Algorithmus kann auch für die Approximation einer konvexen Packung verwendet werden. Diese Möglichkeit wird für die Anwendung auf Kreisen untersucht.