Max Willert

Schranken für eine orthogonale Variante des Chromatischen Art Gallery Problems

Betreuer: Klaus Kriegel
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 09.12.2014

Kurzbeschreibung

In der Arbeit wird das Problem betrachtet, wie man ein einfaches orthogonales Polygon P mit einer endlichen Wächtermenge abdecken kann, bei der jeder Wächter eine von k Farben zugeordnet bekommt. Diese zugehörige Färbung der Wächter heißt konfliktfrei, falls jeder Punkt p in P wenigstens einen Wächter sieht, der einzigartig gefärbt ist unter allen Wächtern, die von p aus sichtbar sind. Für die Anzahl der benötigten Farben konnte eine O(loglog n)-Schranke, sowie eine Omega(loglog n/logloglog n)-Schranke nachgewiesen werden (wobei n die Anzahl der Eckpunkte von P ist). Dabei gingen wir von der r-Sichtbarkeit aus, d.h. dass sich zwei Punkte genau dann sehen, wenn ihr aufgespanntes achsenparalleles Rechteck innerhalb des Polygons liegt. Bei der starken Version unseres Färbungsproblems - das heißt alle Wächter, die von einem Punkt aus gesehen werden, müssen unterschiedliche Farben haben - konnte sogar eine Theta(log n)-Schranke nachgewiesen werden.