3.3 Das Sweep-Line-Prinzip

Idee (Folie 10)

Teste nur Segmente, die nahe beieinander liegen, denn nur die können sich schneiden.

„Nahe beieinander“ wird über eine senkrechte Gerade $L$ präzisiert, die Scan-Line oder Sweep-Line. Sie wird von links nach rechts über die Segmente geschoben.

Sweep-Line-Algorithmen sind ausgabesensitiv: Bei wenigen Schnitten sind sie deutlich schneller als der naive Ansatz.

Drei Klassen von Objekten (Folie 11)

Zu jedem Zeitpunkt teilt $L$ die Segmente in drei Klassen:

Klasse	Lage	Bedeutung
tot (dead)	ganz links von $L$	fertig bearbeitet, nie wieder anfassen
aktiv (active)	schneiden $L$	werden gerade untersucht
inaktiv (inactive)	ganz rechts von $L$	noch nicht erreicht

Der Zustand (state) von $L$ ist die Menge der aktiven Objekte, geordnet nach ihrer Höhe auf $L$.

Ereignispunkte

Der Zustand ändert sich nicht kontinuierlich, sondern nur an bestimmten $x$-Positionen:

• am Startpunkt eines Segments (es wird aktiv),
• am Endpunkt eines Segments (es wird tot),
• und bei beliebigen Segmenten zusätzlich an Schnittpunkten (die Reihenfolge auf $L$ ändert sich, siehe 3.3.2).

Diese Stellen heißen Ereignispunkte (event points). Man muss $L$ also nicht kontinuierlich bewegen, sondern springt von Ereignis zu Ereignis.

Die zwei Datenstrukturen jedes Sweeps

Struktur	Inhalt	Sortiert nach	Typische Umsetzung
Ereignisstruktur $Q$ / ES	kommende Ereignisse	$x$	sortiertes Array, Heap, balancierter Baum
Statusstruktur $L$ / SSS	aktive Segmente	$y$ auf der Sweep-Line	balancierter Suchbaum (AVL, Rot-Schwarz)

Begriffe

Die Folien nennen in 3.3.1 die Struktur für $L$ „event structure“. Gemeint ist der Zustand der Sweep-Line. In 3.3.2 heißt sie dann sauber Scan-Line-State-Structure (SSS), die Ereignisse liegen in der Event Structure (ES).

Wo kommt das Prinzip noch vor? (Ausblick)

Das Sweep-Prinzip taucht in der Vorlesung immer wieder auf:

• Graham's Scan (Kap. 2) ist ein Sweep von links nach rechts mit einem Stack als Status.
• Fortunes Algorithmus für Voronoi-Diagramme (Kap. 5) schiebt eine waagrechte Sweep-Line von oben nach unten. Dort gibt es Punkt- und Kreisereignisse.
• Punktlokalisierung und Polygon-Triangulierung (Kap. 6, 7) nutzen ebenfalls Sweeps.