Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.18419/opus-11365
Autor(en): Owens, Niklas
Titel: Anwendung der Well-Separated Pair Decomposition auf Sichtbarkeitsgraphen
Erscheinungsdatum: 2020
Dokumentart: Abschlussarbeit (Master)
Seiten: 27
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-113827
http://elib.uni-stuttgart.de/handle/11682/11382
http://dx.doi.org/10.18419/opus-11365
Zusammenfassung: Bisherige Ansätze zur Berechnung von Pfaden zwischen zwei Punkten mit mini- maler euklidischer Länge in einer Umgebung mit unpassierbaren Hindernissen basieren oft auf der Konstruktion des vollständigen Sichtbarkeitsgraphen um auf diesem Routing-Algorithmen auszuführen. Problematisch an diesen Verfahren ist zum einen die hohe Berechnungszeit des vollständigen Sichtbarkeitsgraphen, zum anderen, dass die Komplexität des Sichtbarkeitsgraphen in O(n2) liegt. Um dies zu vermeiden, befasst sich diese Arbeit mit der Entwicklung eines Verfahrens zur Konstruktion von Spannern für Sichtbarkeitsgraphen, auf denen kürzeste Pfade approximiert werden können. Anhand experimenteller Vergleiche mit einem naiven Algorithmus hat sich gezeigt, dass die Spannerkonstruktion deutlich schneller ist als die des vollständigen Sichtbarkeitsgraphen, wobei die Läge der approximierten Pfade im Durchschnitt nur geringfügig von der Länge der tatsächlich kürzesten Pfade abweicht.
Enthalten in den Sammlungen:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Abschlussarbeit_Owens.pdf1,13 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.