Logo der Freien Universität BerlinFreie Universität Berlin

Fachbereich Mathematik und Informatik


Service-Navigation

  • Startseite
DE
  • DE: Deutsch
  • EN: English
Hinweise zur Datenübertragung bei der Google™ Suche
Fachbereich Mathematik und Informatik/Informatik/

Theoretische Informatik

Menü
  • Mitglieder

    loading...

  • Projekte

    loading...

  • Gäste

    loading...

  • Abschlussarbeiten

    loading...

  • Fotoalbum

    loading...

  • Veranstaltungen

    loading...

  • Software

    loading...

  • Stipendienprogramme

    loading...

  • Archiv

    loading...

Mikronavigation

  • Startseite
  • Informatik
  • Arbeitsgruppen
  • Theoretische Informatik
  • Abschlussarbeiten
  • Abgeschlossene Bachelorarbeiten
  • Attraktorbasierte Überdeckung orthogonaler Polygone

Marvin Becker:

Attraktorbasierte Überdeckung orthogonaler Polygone

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.  

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

Service-Navigation

  • Startseite

Diese Seite

  • Drucken
  • RSS-Feed abonnieren
  • English