Alexander Kauer

Implementation of and Experiments on Centerpoint Approximation Algorithms

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 17.02.2015

Kurzbeschreibung

Der eindimensionale Median ist einer der grundlegenden Bestandteile der Informatik und Mathematik. Die Idee des Medians kann auf höhere Dimensionen als Centerpoint verallgemeinert werden. Hierbei zerlegen alle Hyperebenen durch einen Centerpoint die Eingabe in zwei etwa gleich große Teile.

Der bisher schnellste Algorithmus um einen Centerpoint für n Punkte in d Dimensionen zu finden hat eine erwartete Laufzeit von O(n^(d - 1)). Durch die in d exponentielle Laufzeit ist dieser Algorithmus nur für kleinere Dimensionen sinnvoll anwendbar. Es ist kein Algorithmus bekannt um einen Centerpoint in polynomieller Laufzeit bezüglich sowohl n als auch beliebiger Dimension d zu finden. Aus diesem Grund sind vor allem approximative Algorithmen für dieses Themengebiet von großem Interesse.

In dieser Arbeit werden mehrere approximative Algorithmen für eine beliebige Anzahl an Dimensionen vorgestellt. Diese Algorithmen haben ein bezüglich Anzahl der Punkte n und der Dimension d polynomielles Laufzeitverhalten. Weiterhin wurden diese Algorithmen implementiert und deren durchschnittliche Güte bei zufälliger Eingabe ermittelt, da die Algorithmen nur eine untere Schranke der Güte des Ergebnisses garantieren.