Yussuf Kassem:

Approximation von Kreispackungen

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.

Abschluss
Bachelor of Science (B.Sc.)
Abgabedatum
15.02.2016