Sweep (Informatik)

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 ${\displaystyle n}$-dimensionales statisches Problem in ein (n-1)-dimensionales dynamisches Problem umgewandelt.

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

Sweep-Algorithmen

Für d​as Lösen folgender zweidimensionaler Probleme g​ibt es bekannte u​nd zeiteffiziente Sweep-Algorithmen:

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

Literatur

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