Sweep (Informatik)

Animation eines Sweep-Algorithmus, der ein Voronoi-Diagramm konstruiert (Algorithmus von Fortune)

Als Sweep, Sweep-Verfahren oder manchmal auch Scan-Verfahren wird ein Paradigma in der Informatik verstanden, das beim Design von Algorithmen Anwendung findet. Ein derartiger Algorithmus wird auch Sweep-Algorithmus genannt. Kern eines Sweep im Zweidimensionalen ist die Sweep-Line (Sweep-Gerade) bzw. im Dreidimensionalen die Sweep-Plane (Sweep-Ebene). Durch sie wird der Raum „ausgefegt“, das heißt, man bewegt sie durch den gesamten Raum, bis alle Objekte des Problems besucht und verarbeitet wurden. Dazu wird eine Datenstruktur verwendet, die die von der Sweep-Line oder -Plane berührten Objekte speichert. Eine solche Datenstruktur wird dann als Sweep-Status-Struktur bezeichnet. Besonders häufig werden dadurch Probleme der Algorithmischen Geometrie gelöst. Allgemein wird bei einem Sweep ein $n$-dimensionales statisches Problem in ein (n-1)-dimensionales dynamisches Problem umgewandelt.

Sweep-Algorithmen

Für das Lösen folgender zweidimensionaler Probleme gibt es bekannte und zeiteffiziente Sweep-Algorithmen:

• Bestimmung der Schnittpunkte von Liniensegmenten, Zeitkomplexität ${\mathcal {O}}((n+h)\log n)$
• Konstruktion eines Voronoi-Diagramms, in ${\mathcal {O}}(n\log n)$-Zeit
• Durchschnitt zweier Polygone, in ${\mathcal {O}}((n+k)\log n)$-Zeit, wobei k die Anzahl der Kantenschnittpunkte beider Polygone ist
• Dichtestes Punktpaar in der Ebene, ${\mathcal {O}}(n\log n)$

Literatur

• Rolf Klein: Algorithmische Geometrie. Springer Verlag (2005), ISBN 978-3-540-20956-0.