Kapitel 3 – Schnitt von Liniensegmenten

Folien: 📄 03-intersection.pdf · Praktikumsaufgabe 2 (iso-orientierte Segmente)

Gegeben sind $n$ Strecken in der Ebene, gesucht sind alle Schnittpunkte. Das klingt nach einem einfachen Doppel-for. An diesem Problem lernt man aber die wichtigste Technik der algorithmischen Geometrie: das Sweep-Line-Prinzip (auf den Folien Scan-Line).

Die Grundidee: Man schiebt eine senkrechte Gerade von links nach rechts über die Ebene. Sie hält nur an endlich vielen Ereignispunkten. Dort wird eine kleine, geordnete Datenstruktur aktualisiert. Statt jedes Paar zu testen, testet man nur Segmente, die auf der Sweep-Line benachbart sind.

Aufbau

Abschnitt	Inhalt	Laufzeit
3.1–3.2 Motivation & naiver Ansatz	GIS-Überlagerung, alle Paare testen	$\Theta(n^2)$
3.3 Sweep-Line-Prinzip	tote / aktive / inaktive Objekte, Ereignispunkte	–
3.3.1 Iso-orientierte Segmente	waagrechte und senkrechte Segmente, Bereichssuche im Baum	$O(n\log n + R)$
3.3.2 Beliebige Segmente	Bentley–Ottmann: Schnittpunkte als Ereignisse	$O((n+k)\log n)$
Anhang: AVL-Bäume & Heaps	die Datenstrukturen hinter Status und Ereignisliste	$O(\log n)$ pro Operation

$n$ = Anzahl der Segmente, $R$ bzw. $k$ = Anzahl der Schnitte (Ausgabegröße).

Merksatz

Sweep-Line = Ereignisstruktur (Wann muss ich anhalten? Sortiert nach $x$) + Statusstruktur (Was schneidet die Sweep-Line gerade? Sortiert nach $y$).