Marvin Becker

Attraktorbasierte Überdeckung orthogonaler Polygone

Betreuer: Frank Hoffmann
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 15.02.2017

Kurzbeschreibung

In der Bachelorarbeit diskutieren wir die Attraktor-Überdeckung und das Attraktor-Routing in einfachen orthogonalen Polygonen. Diese beiden Probleme sind Varianten des klassischen Art Gallery Theorems. Bei der Attraktor-Überdeckung ist es das Ziel, das Innere eines solchen Polygons mit Attraktoren zu überdecken. Attraktoren ("beacons") sind dabei Punkte innerhalb des Polygons, die, wenn aktiviert, alle anderen Punkte innerhalb des Polygons auf direktem Wege anziehen. Das Attraktor-Routing-Problem beschäftigt sich mit der Frage, wie viele Attraktoren nötig sind, um zwischen zwei beliebigen Punkten innerhalb des Polygons zu routen. Einen Punkt zu einem Zielpunkt zu routen beschreibt dabei den Prozess, diesen Punkt durch sequentielle Aktivierung einer Menge von Attraktoren zu seinem Ziel zu leiten. Zu beiden Fragen werden in der Arbeit die kürzlich von Bae et al. bzw. von Shermer bewiesenen optimalen worst-case-Schranken vorgestellt. Zudem führen wir ein neues, stärkeres Modell des Attraktor-Routings ein und beweisen eine untere Schranke für den worst case.