Sweep (Informatik)

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, welches 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 Θ(nlog n)
  • Konstruktion eines Voronoi-Diagramms, in O(nlog n) Zeit
  • Durchschnitt zweier Polygone, in O((n + k)log n) Zeit, wobei k die Anzahl der Kantenschnittpunkte beider Polygone ist
  • Dichtestes Punktpaar in der Ebene O(nlogn)

Literatur


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Sweep — bezeichnet: Sweep (Sport), eine Siegesserie im Sport Sweep (Grafik), ein Verfahren in der Computergrafik Sweep Picking, eine Spieltechnik der Gitarre Sweep (Informatik), ein Verfahren in der Informatik Sweep (Software), ein Audioeditor für Linux… …   Deutsch Wikipedia

  • Delaunay Triangulation — Delaunay Triangulation, oft auch nur Triangulation oder Triangulierung genannt, ist ein gebräuchliches Verfahren, um aus einer Punktemenge ein Dreiecksnetz zu erstellen. Sie ist nach dem russischen Mathematiker Boris Nikolajewitsch Delone… …   Deutsch Wikipedia

  • Tourenplanungssoftware — Unter Tourenplanung versteht man das Problem, eine möglichst gute Zuordnung von Fahrzeugen zu Aufträgen und für jedes Fahrzeug eine optimale Reihenfolge der zu bedienenden Auftragsstandorte zu finden. Ein Auftrag besteht meist darin, eine… …   Deutsch Wikipedia

  • Correlation — In probability theory and statistics, correlation, (often measured as a correlation coefficient), indicates the strength and direction of a linear relationship between two random variables. In general statistical usage, correlation or co relation …   Wikipedia

  • Automatische Speicherbereinigung — Garbage Collection (GC, auch Automatische Speicherbereinigung oder Freispeichersammlung) ist ein Fachbegriff aus der Softwaretechnik. Er steht für ein Verfahren zur regelmäßigen automatischen Wiederverfügbarmachung von nicht mehr benötigtem… …   Deutsch Wikipedia

  • Finalisierung — Garbage Collection (GC, auch Automatische Speicherbereinigung oder Freispeichersammlung) ist ein Fachbegriff aus der Softwaretechnik. Er steht für ein Verfahren zur regelmäßigen automatischen Wiederverfügbarmachung von nicht mehr benötigtem… …   Deutsch Wikipedia

  • Garbage-Collection — (GC, auch Automatische Speicherbereinigung oder Freispeichersammlung) ist ein Fachbegriff aus der Softwaretechnik. Er steht für ein Verfahren zur regelmäßigen automatischen Wiederverfügbarmachung von nicht mehr benötigtem Speicher und anderen… …   Deutsch Wikipedia

  • Garbage-Collector — Garbage Collection (GC, auch Automatische Speicherbereinigung oder Freispeichersammlung) ist ein Fachbegriff aus der Softwaretechnik. Er steht für ein Verfahren zur regelmäßigen automatischen Wiederverfügbarmachung von nicht mehr benötigtem… …   Deutsch Wikipedia

  • Garbage Collector — Garbage Collection (GC, auch Automatische Speicherbereinigung oder Freispeichersammlung) ist ein Fachbegriff aus der Softwaretechnik. Er steht für ein Verfahren zur regelmäßigen automatischen Wiederverfügbarmachung von nicht mehr benötigtem… …   Deutsch Wikipedia

  • Garbage collection — (GC, auch Automatische Speicherbereinigung oder Freispeichersammlung) ist ein Fachbegriff aus der Softwaretechnik. Er steht für ein Verfahren zur regelmäßigen automatischen Wiederverfügbarmachung von nicht mehr benötigtem Speicher und anderen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”