Fortunes-algorithm
Relevante Artikel
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 -dimensionales statisches Problem in ein (n-1)-dimensionales dynamisches Problem umgewandelt. .. weiterlesen