imported>Kmschaal: Replaced animation with a more sophisticated version for better illustration

2023-04-24T15:58:56Z

Replaced animation with a more sophisticated version for better illustration

Neue Seite

[[Datei:Sweep-line-algorithm.gif|frame|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 [[Algorithmus|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 [[Algorithmische Geometrie|Algorithmischen Geometrie]] gelöst. Allgemein wird bei einem Sweep ein <math>n</math>-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 <math>\mathcal{O}((n+h) \log n)</math>
* Konstruktion eines [[Voronoi-Diagramm]]s, in <math>\mathcal{O}(n \log n)</math>-Zeit
* Durchschnitt zweier Polygone, in <math>\mathcal{O}((n+k) \log n)</math>-Zeit, wobei k die Anzahl der Kantenschnittpunkte beider Polygone ist
* [[Dichtestes Punktpaar]] in der Ebene, <math>\mathcal{O}(n \log n)</math>

== Literatur ==
* Rolf Klein: ''Algorithmische Geometrie.'' Springer Verlag (2005), ISBN 978-3-540-20956-0.

[[Kategorie:Algorithmische Geometrie]]

Sweep (Informatik) - Versionsgeschichte

imported>Kmschaal: Replaced animation with a more sophisticated version for better illustration