Anwendung der Well-Separated Pair Decomposition auf Sichtbarkeitsgraphen

Abstract

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.