Sweep (Informatik)

Grundidee und Funktionsweise

Ein Sweep, auch Sweep-Verfahren oder Scan-Verfahren genannt, ist ein Paradigma zum Entwurf von Algorithmen. Besonders häufig wird es in der algorithmischen Geometrie eingesetzt. Im Zweidimensionalen bewegt sich eine Sweep-Line (Sweep-Gerade) durch den gesamten Raum; im Dreidimensionalen übernimmt diese Aufgabe eine Sweep-Plane (Sweep-Ebene). Der Raum wird dabei schrittweise „ausgefegt“, bis alle relevanten Objekte besucht und verarbeitet wurden.

Während des Vorgangs speichert eine Datenstruktur die Objekte, die von der Sweep-Line oder Sweep-Plane berührt werden. Diese Datenstruktur heißt Sweep-Status-Struktur. Allgemein wird durch einen Sweep ein n-dimensionales statisches Problem in ein (n−1)-dimensionales dynamisches Problem umgewandelt. Eine Animation des Algorithmus von Fortune zeigt beispielsweise, wie ein Voronoi-Diagramm mit einem Sweep-Algorithmus konstruiert wird.

Bekannte zweidimensionale Anwendungen

Für verschiedene zweidimensionale Probleme gibt es bekannte und zeiteffiziente Sweep-Algorithmen:

• Schnittpunkte von Liniensegmenten lassen sich mit einer Zeitkomplexität von O((n+h) log n) bestimmen.
• Ein Voronoi-Diagramm kann in O(n log n)-Zeit konstruiert werden.
• Der Durchschnitt zweier Polygone kann in O((n+k) log n)-Zeit berechnet werden. Dabei bezeichnet k die Anzahl der Kantenschnittpunkte beider Polygone.
• Das dichteste Punktpaar in der Ebene kann in O(n log n)-Zeit bestimmt werden.