Spickzettel

Zum schnellen Nachschlagen in der Vorlesung. Alles Wichtige auf einer Seite, mit Links zur ausführlichen Erklärung.

Schneller finden

/ oder Strg+K öffnet die Suche überall auf der Seite. Tippfehler sind egal („vornoi“, „bentley otman“), mehrere Wörter grenzen ein („kd laufzeit“).

Algorithmen auf einen Blick

Problem	Algorithmus	Zeit	Speicher	Kernidee
Konvexe Hülle	naiv	$O(n^3)$	$O(n)$	jedes Paar: liegen alle anderen rechts?
Konvexe Hülle	Graham's Scan	$O(n\log n)$	$O(n)$	nach $x$ sortieren, Stack, nur Rechtskurven
Konvexe Hülle	Jarvis' March	$O(nh)$	$O(n)$	Geschenkpapier: nächste Ecke = alle anderen rechts
Konvexe Hülle	Chan	$O(n\log h)$	$O(n)$	Gruppen + Graham, Jarvis mit binärer Suche, $H=2^{2^t}$
Konvexe Hülle	untere Schranke	$\Omega(n\log n)$		Sortieren → Punkte auf Parabel $y=x^2$
Segmentschnitt	naiv	$O(n^2)$		alle Paare
Segmentschnitt iso	Sweep	$O(n\log n+R)$	$O(n)$	Horizontale in Baum, Vertikale = Bereichsanfrage
Segmentschnitt allg.	Bentley–Ottmann	$O((n+k)\log n)$	$O(n+k)$ (Folien: $O(n^2)$)	nur Nachbarn in der Statusstruktur testen
1d-Bereich	balancierter Baum	$O(\log n+R)$	$O(n)$	Split-Knoten, zwei Pfade
2d-Bereich	kd-Baum	$O(\sqrt n+R)$, Aufbau $O(n\log n)$	$O(n)$	abwechselnd $x$/$y$ am Median teilen
2d-Bereich	Range-Tree	$O(\log^2 n+R)$, Aufbau $O(n\log n)$	$O(n\log n)$	$x$-Baum, pro Knoten $y$-Baum der kanonischen Teilmenge
$k$d-Bereich	kd-Baum	$O(n^{1-1/k}+R)$	$O(n)$
$k$d-Bereich	Range-Tree	$O(\log^k n+R)$	$O(n\log^{k-1} n)$
Voronoi	Halbebenen	$O(n^2\log n)$		jede Zelle = Schnitt von $n-1$ Halbebenen
Voronoi	Fortune	$O(n\log n)$	$O(n)$	Sweep, Strandlinie aus Parabeln, Punkt-/Kreisereignisse
Delaunay	randomisiert inkrementell	erw. $O(n\log n)$, naiv $O(n^2)$	$O(n)$	schlechte Dreiecke raus, Loch fächern

$n$ = Eingabegröße, $h$ = Hüllpunkte, $R$/$k$ = Größe der Ausgabe.

Formeln

Was	Formel
Orientierung	$\operatorname{orient}(p,q,r) = (q_x-p_x)(r_y-p_y)-(q_y-p_y)(r_x-p_x)$; $>0$ links, $<0$ rechts, $=0$ kollinear
InCircle	$\det$ der Zeilen $(a_x-d_x,\ a_y-d_y,\ \lvert a-d\rvert^2)$ usw.; $>0$ ⇔ $d$ im Umkreis des ccw-Dreiecks $abc$
Master-Theorem	$T(n)=aT(n/b)+f(n)$, $\alpha=\log_b a$: $f\ll n^\alpha$ → $n^\alpha$; $f\approx n^\alpha$ → $n^\alpha\log n$; $f\gg n^\alpha$ → $f$
kd-Baum-Gerade	$Q(n)=2+2Q(n/4)=O(\sqrt n)$
Strandlinie	$\beta(x)=\dfrac{(x-p_x)^2+p_y^2-\ell_y^2}{2(p_y-\ell_y)}$
Voronoi-Größe	$\le 2n-5$ Knoten, $\le 3n-6$ Kanten (Euler $V-E+F=2$ mit $v_\infty$)
Triangulierung	$2n-2-h$ Dreiecke, $3n-3-h$ Kanten
Strandlinie	$\le 2n-1$ Bögen
Delaunay-Schritt	erwartet $< 6$ neue Dreiecke (Durchschnittsgrad)

Allgemeine Lage: was jeder Algorithmus annimmt

Algorithmus	Annahme	Wenn verletzt …
Graham	keine zwei Punkte mit gleichem $x$	lexikographisch nach $(x,y)$ sortieren
Graham/Jarvis	keine drei kollinear	kollinear als „keine Rechtskurve“ werten bzw. den weitesten nehmen
Iso-Segmente	keine gemeinsamen $x$-Koordinaten von Endpunkten	bei gleichem $x$: Einfügen → Anfragen → Löschen
Bentley–Ottmann	keine Senkrechten, keine 3 Segmente durch einen Punkt, keine Überlappung	lexikographische Ordnung, Ereignis mit Segmentliste
kd-Baum	alle Koordinaten verschieden	<= / >= in der Suche
Fortune	keine 4 Punkte auf einem Kreis, keine gleichen $y$	Kanten der Länge 0, Bögen der Länge 0
Delaunay	keine 4 Punkte auf einem Kreis	Fläche beliebig triangulieren, Ergebnis nicht eindeutig

Sätze, die man nennen können sollte

• Ω(n log n) für Hülle: Reduktion von Sortieren (2.3).
• Graham ist optimal, Jarvis/Chan sind ausgabesensitiv.
• kd-Baum $O(\sqrt n+R)$ wegen $Q(n)=2+2Q(n/4)$.
• Range-Tree Speicher $O(n\log n)$: jeder Punkt auf jeder Ebene in genau einer kanonischen Teilmenge.
• Satz 1 (Voronoi): kollinear → $n-1$ parallele Geraden, sonst zusammenhängend mit Strecken/Halbgeraden.
• Satz 3 (Voronoi): Knoten ⇔ leerer Kreis mit ≥ 3 Punkten, Kante ⇔ leerer Kreis mit genau 2.
• Lemma 4–6 (Fortune): Bögen entstehen nur durch Punktereignisse, verschwinden nur durch Kreisereignisse, alle Knoten werden gefunden.
• Satz 7: Fortune $O(n\log n)$, $O(n)$ Speicher, optimal.
• Satz 8: Delaunay ⇔ leerer Umkreis.
• Satz 9: Delaunay maximiert den kleinsten Winkel.
• Satz 11: Algorithmus 4 ist korrekt (neue Kanten im Loch, neue Dreiecke legal).

Glossar Deutsch – Englisch

Deutsch	Englisch	Bedeutung
konvexe Hülle	convex hull	kleinste konvexe Menge um alle Punkte
Orientierungstest	orientation test / orient2d	links/rechts/kollinear über Determinante
allgemeine Lage	general position	keine Degenerationen (kollinear, kozirkulär …)
ausgabesensitiv	output-sensitive	Laufzeit hängt von der Ausgabegröße ab
Sweep-Line / Scan-Line	sweep line	fegende Gerade, hält nur an Ereignissen
Ereignisstruktur	event queue	sortierte Haltepunkte (Heap)
Statusstruktur	status structure (SSS)	aktive Objekte entlang der Sweep-Line (balancierter Baum)
Bereichsanfrage	range query	alle Punkte in einem Rechteck
kanonische Teilmenge	canonical subset	Blätter unter einem Knoten
assoziierte Struktur	associated structure	zweite Ebene im Range-Tree
Split-Knoten	split node	wo sich die Suchpfade zu $x_l$ und $x_r$ trennen
Zelle	cell / region	Teil der Ebene, der zu einem Knoten oder Site gehört
Datenpunkt	site	Eingabepunkt beim Voronoi-Diagramm
Mittelsenkrechte	bisector	Punkte mit gleichem Abstand zu zwei Sites
Strandlinie	beach line	untere Einhüllende der Parabeln bei Fortune
Bogen	arc	ein Parabelstück der Strandlinie
Punktereignis	site event	Sweep-Line erreicht einen Site
Kreisereignis	circle event	Bogen verschwindet, Voronoi-Knoten entsteht
falscher Alarm	false alarm	Kreisereignis, das ungültig wurde
doppelt verkettete Kantenliste	DCEL (doubly connected edge list)	Datenstruktur für planare Unterteilungen
dualer Graph	dual graph	Knoten ↔ Flächen vertauscht
Delaunay-Bedingung	empty circle property	kein Punkt im Umkreis
illegale Kante	illegal edge	verletzt lokal die Delaunay-Bedingung, wird geflippt
Kantenflip	edge flip	Diagonale eines konvexen Vierecks tauschen
Rückwärtsanalyse	backward analysis	Erwartungswert über den zuletzt eingefügten Punkt
Punktlokalisierung	point location	in welcher Fläche liegt ein Punkt? (Kap. 6)

Praktikum

#	Aufgabe	Nachlesen
1	Graham + Jarvis	2.4, 2.5
2	iso-orientierte Segmente	3.3.1
3	2d-Baum	4.3
4	randomisierte Delaunay-Triangulierung	5.4