Mündliche Prüfung – Fragen & Tipps

Format: mündlich, Einzeltermin, ca. 40 Minuten, ohne Hilfsmittel. Man hat also Papier oder Tafel und den eigenen Kopf.

Stand

Hier sind die Kapitel 0–5 abgedeckt (bis Voronoi/Delaunay). Punktlokalisierung (§6), Polygon-Triangulierung (§7) und 3D-Hüllen (§8) kommen noch dazu, sobald sie im Skript stehen. Die Fragen sind selbst zusammengestellt aus den Folien, nicht von Prof. Umlauf.

Wie läuft so eine Prüfung typischerweise?

• Einstieg mit einem Thema deiner Wahl ist an vielen Lehrstühlen üblich. Frag vorher nach, ob das hier auch so ist. Wenn ja: ein Thema vorbereiten, das du an der Tafel in 5 Minuten sauber aufbauen kannst (z.B. Graham's Scan oder Fortune).
• Danach springt der Prüfer meist durch die Kapitel. Pro Kapitel ein bis zwei Fragen, oft in der Form „Erklären Sie X“ → „Warum ist das so?“ → „Was passiert wenn …?“.
• Bei Umlauf liegt der Fokus erfahrungsgemäß auf Algorithmus + Laufzeit + Begründung, nicht auf auswendig gelernten Folien.

Hints für die Prüfung

1. Immer zuerst eine Skizze. Bevor du einen Algorithmus erklärst, ein Beispiel mit 5–8 Punkten zeichnen. Daran erklären ist viel leichter als abstrakt, und der Prüfer sieht sofort, dass du es verstanden hast.
2. Laufzeit immer mit Begründung. Nicht nur „$O(n\log n)$“, sondern „Sortieren dominiert, der Scan selbst ist amortisiert linear, weil jeder Punkt höchstens einmal gepusht und einmal gepoppt wird“.
3. Das Schema für jeden Algorithmus: Problem → Idee → Datenstrukturen → Ablauf → Laufzeit → Speicher → Sonderfälle → untere Schranke/Optimalität. Wenn du hängst, gehe einfach die nächste Station durch.
4. Allgemeine Lage benennen. Fast jeder Algorithmus nimmt etwas an (keine drei Punkte kollinear, keine zwei gleichen $x$-Koordinaten, keine vier Punkte auf einem Kreis …). Sag welche Annahme, warum sie gebraucht wird und wie man sie in der Implementierung los wird. Das ist die typische Nachfrage.
5. Die Praktikumsaufgaben sind Prüfungsstoff. Du hast Graham/Jarvis, iso-orientierte Segmente, kd-Baum und Delaunay selbst implementiert. Erzähl ruhig, welche Sonderfälle dir beim Implementieren begegnet sind. Das wirkt souverän.
6. Beweise, die man können sollte (kurz, an der Tafel machbar):
   • untere Schranke $\Omega(n\log n)$ für die konvexe Hülle (Reduktion von Sortieren, Parabel $y=x^2$),
   • Graham amortisiert $O(n)$ nach dem Sortieren,
   • kd-Baum $O(\sqrt n+R)$ über $Q(n)=2+2Q(n/4)$,
   • Range-Tree Speicher $O(n\log n)$ und Anfrage $O(\log^2 n+R)$,
   • Voronoi $\le 2n-5$ Knoten, $\le 3n-6$ Kanten (Euler + $v_\infty$),
   • Fortune $O(n\log n)$ und warum das optimal ist,
   • Korrektheit von Bowyer–Watson (Satz 11).
7. Bekannte Fallen:
   • kd-Baum: welche Koordinate an der Wurzel (Folien: $y$, de Berg: $x$), und dass strikte Vergleiche < bei gleichen Koordinaten Punkte verlieren.
   • Bentley–Ottmann: Schnittpunkte links von der Sweep-Line nicht als Ereignis einfügen, Duplikate vermeiden.
   • Fortune: der Voronoi-Knoten ist der Kreismittelpunkt, das Ereignis passiert am tiefsten Punkt des Kreises.
   • Delaunay: Zufällige Reihenfolge ist nötig für die erwartete Laufzeit, nicht nur nett.
8. Ehrlich sein, wenn man etwas nicht weiß, und laut weiterdenken. „Ich weiß den Beweis nicht auswendig, aber die Idee ist …“ ist in einer mündlichen Prüfung viel besser als Schweigen.
9. Zahlen bereithalten: $\sqrt{10^6}=10^3$, $\log_2 10^6\approx 20$. Damit kann man Laufzeiten anschaulich vergleichen.

Fragen nach Kapitel

Antworten zum Aufklappen. Erst selbst laut beantworten (am besten mit Skizze), dann nachsehen.

Kapitel 1 – Grundlagen

Was ist der Unterschied zwischen Punkten und Vektoren? Warum ist das wichtig?

Punkte sind Orte im affinen Raum, Vektoren sind Verschiebungen. Erlaubt sind Punkt − Punkt = Vektor, Punkt + Vektor = Punkt, und affine Kombinationen $\sum\alpha_ip_i$ mit $\sum\alpha_i=1$ (z.B. Mittelpunkt). Punkt + Punkt ist nicht definiert (hängt vom Koordinatenursprung ab). Wichtig, weil geometrische Algorithmen unabhängig vom Koordinatensystem sein sollen. → 1.2.1

Wie testet man, ob ein Punkt links oder rechts einer gerichteten Geraden liegt?

Mit dem Orientierungstest, der Determinante $\operatorname{orient}(p,q,r)=\det\begin{pmatrix}q_x-p_x & r_x-p_x\\ q_y-p_y & r_y-p_y\end{pmatrix}$ $>0$: $r$ links (Linkskurve, gegen den Uhrzeigersinn), $<0$: rechts, $=0$: kollinear. Es ist das $z$ des Kreuzprodukts bzw. die doppelte vorzeichenbehaftete Dreiecksfläche. Kommt ohne Winkel, Wurzeln oder Division aus. → 1.2.2

Was ist die Real RAM und wo ist sie unrealistisch?

Rechenmodell: Speicherzellen enthalten reelle Zahlen mit unendlicher Genauigkeit, Grundrechenarten und Vergleiche kosten $O(1)$. In echt hat man Gleitkommazahlen, Rundungsfehler können den Orientierungstest bei fast kollinearen Punkten falsch machen. Abhilfe: exakte Arithmetik (Ganzzahlen, adaptive Prädikate nach Shewchuk), Epsilon-Toleranzen (gefährlich, nicht transitiv). → 1.2.3

Erklären Sie O, Ω, Θ. Was sagt das Master-Theorem?

$O$ obere, $\Omega$ untere, $\Theta$ exakte asymptotische Schranke (bis auf Konstanten, ab einem $n_0$). Master-Theorem für $T(n)=aT(n/b)+f(n)$ mit $\alpha=\log_b a$: Fall 1 $f$ polynomiell kleiner als $n^\alpha$ → $\Theta(n^\alpha)$; Fall 2 gleich → $\Theta(n^\alpha\log n)$; Fall 3 polynomiell größer (+ Regularität) → $\Theta(f(n))$. Beispiele: Mergesort Fall 2, kd-Baum-Gerade $Q(n)=2Q(n/4)+O(1)$ Fall 1 → $\sqrt n$. → 1.2.6

Kapitel 2 – Konvexe Hülle

Definieren Sie Konvexität und konvexe Hülle.

$S$ konvex ⇔ für alle $p,q\in S$ liegt die Strecke $\overline{pq}$ in $S$. Die konvexe Hülle $\mathcal{CH}(P)$ ist die kleinste konvexe Menge, die $P$ enthält = Schnitt aller konvexen Obermengen = Menge aller Konvexkombinationen. In 2d ein konvexes Polygon mit Ecken aus $P$ (Gummiband). Ausgabe: Ecken im Uhrzeigersinn (oder gegen). → 2.1

Wie funktioniert der naive Algorithmus und wie schnell ist er?

Für jedes geordnete Paar $(p,q)$ prüfen, ob alle anderen Punkte rechts von $\overrightarrow{pq}$ liegen. Wenn ja, ist $\overrightarrow{pq}$ eine Hüllkante. $n^2$ Paare × $n$ Tests = $O(n^3)$, dann Kanten sortieren. Problem: kollineare Punkte auf dem Rand. → 2.2

Beweisen Sie: Die konvexe Hülle braucht Ω(n log n).

Reduktion von Sortieren: Zahlen $x_1,\dots,x_n$ auf die Parabel abbilden, $p_i=(x_i,x_i^2)$, in $O(n)$. Alle liegen auf der Hülle (Parabel ist konvex). Hülle berechnen, beim kleinsten $x$ starten und den Rand ablaufen ergibt die sortierte Folge in $O(n)$. Ginge die Hülle schneller als $n\log n$, ginge auch Sortieren schneller, Widerspruch zur unteren Schranke $\Omega(n\log n)$ für vergleichsbasiertes Sortieren. → 2.3

Erklären Sie Graham's Scan inklusive Laufzeit.

Punkte nach $x$ sortieren (lexikographisch, bei gleichem $x$ nach $y$). Obere Hülle von links nach rechts: Punkt pushen, solange die letzten drei keine Rechtskurve machen, den mittleren poppen. Dann untere Hülle von rechts nach links, beide zusammenfügen. Laufzeit: Sortieren $O(n\log n)$, der Scan ist amortisiert $O(n)$, weil jeder Punkt höchstens einmal gepusht und gepoppt wird. Optimal wegen 2.3. Kollineare Punkte: als „keine Rechtskurve“ werten, dann werden sie entfernt. → 2.4

Jarvis' March: Idee, Laufzeit, wann besser als Graham?

Geschenkpapier-Algorithmus: Beim Punkt mit kleinstem $x$ starten. Von der aktuellen Ecke den Punkt suchen, so dass alle anderen rechts liegen (kleinster Winkel, per Orientierungstest), weitergehen, bis man wieder am Start ist. $O(n)$ pro Ecke, also $O(nh)$ bei $h$ Hüllpunkten: ausgabesensitiv. Besser als Graham, wenn $h<\log n$; schlechter, wenn alle Punkte auf der Hülle liegen ($O(n^2)$). → 2.5

Wie schafft Chan's Algorithmus O(n log h)? Warum widerspricht das nicht Ω(n log n)?

Punkte in $n/m$ Gruppen der Größe $m$ teilen, jede mit Graham ($O(n\log m)$). Dann Jarvis über die Gruppen: pro Schritt in jeder Teilhülle per binärer Suche die Tangente finden ($O(\frac nm\log m)$ pro Schritt). Nach $H$ Schritten abbrechen. $H=m$ raten und quadrieren ($H=2^{2^t}$), dann bilden die Kosten eine geometrische Reihe: $O(n\log h)$. Kein Widerspruch, weil die untere Schranke für $h=n$ gilt (Parabel), dann ist $n\log h=n\log n$. → 2.6

Kapitel 3 – Schnitt von Liniensegmenten

Was ist das Sweep-Line-Prinzip? Welche Datenstrukturen braucht man?

Eine Gerade fegt über die Ebene. Statt alle Paare zu testen, betrachtet man nur Objekte, die die Sweep-Line gleichzeitig schneiden. Drei Klassen: erledigt (links), aktiv (geschnitten), noch nicht gesehen (rechts). Zwei Strukturen: Ereignisstruktur (Haltepunkte, sortiert, z.B. Heap/sortierte Liste) und Statusstruktur (aktive Objekte entlang der Sweep-Line, balancierter Suchbaum). → 3.3

Wie findet man alle Schnitte iso-orientierter Segmente in O(n log n + R)?

Sweep von links nach rechts. Ereignisse: linker Endpunkt einer Horizontalen → $y$ in $L$ einfügen; rechter Endpunkt → aus $L$ löschen; Vertikale → Bereichsanfrage $[y_u,y_o]$ in $L$. $L$ als balancierter Suchbaum: Einfügen/Löschen $O(\log n)$, Bereichsanfrage $O(\log n+R_i)$. Sortieren $O(n\log n)$. Gesamt $O(n\log n+R)$. Reihenfolge bei gleichem $x$: erst Einfügen, dann Vertikale, dann Löschen (sonst gehen Berührungen verloren). → 3.3.1

Erklären Sie Bentley–Ottmann. Warum reicht es, Nachbarn zu testen?

Beobachtung: Kurz vor einem Schnittpunkt sind die beiden Segmente in der Statusstruktur benachbart. Also reicht es, Nachbarn auf Schnitt zu testen, und zwar immer dann, wenn sich die Nachbarschaft ändert: beim Einfügen (neues Segment mit oberem und unterem Nachbarn), beim Löschen (die beiden ehemaligen Nachbarn), beim Schnittereignis (Segmente tauschen, je mit neuem äußeren Nachbarn). Ereignisse: linke Endpunkte, rechte Endpunkte, Schnittpunkte (dynamisch). Laufzeit $O((n+k)\log n)$. Annahmen: keine senkrechten Segmente, keine drei Segmente durch einen Punkt, keine Überlappungen, Endpunkte nicht auf anderen Segmenten. → 3.3.2

Ist O((n+k) log n) immer besser als der naive Algorithmus?

Nein. Bei $k=\Theta(n^2)$ Schnitten ist es $O(n^2\log n)$, schlechter als naiv $O(n^2)$. Lohnt sich bei wenigen Schnitten ($k=o(n^2/\log n)$). Optimal wäre $O(n\log n+k)$ (Chazelle–Edelsbrunner, Balaban), aber kompliziert. → 3.3.2

Was ist ein AVL-Baum, wie bleibt er balanciert?

Binärer Suchbaum, in dem sich die Höhen der beiden Teilbäume jedes Knotens um höchstens 1 unterscheiden. Höhe $O(\log n)$. Nach Einfügen/Löschen den Pfad hoch prüfen und mit Einfach- oder Doppelrotationen reparieren (LL/RR einfach, LR/RL doppelt). → Anhang

Kapitel 4 – Bereichsanfragen

Wie ist ein 2d-Baum aufgebaut und wie sucht man darin?

Binärer Baum, jeder Knoten speichert einen Punkt und teilt seine Zelle abwechselnd nach $x$ und $y$. Balanciert durch Teilen am Median (zwei vorsortierte Listen, stabil aufteilen): Aufbau $O(n\log n)$, Speicher $O(n)$. Suche: Punkt melden, falls in $D$; links weiter, wenn $D$ unter den Schlüssel reicht; rechts, wenn darüber. → 4.3

Beweisen Sie die Anfragezeit O(√n + R) beim 2d-Baum.

Teuer sind nur Knoten, deren Zelle vom Rand von $D$ geschnitten wird. Zähle Zellen, die eine senkrechte Gerade trifft: Nach zwei Ebenen ($x$ und $y$) gibt es 4 Enkel mit je $n/4$ Punkten, die Gerade trifft höchstens 2. $Q(n)=2+2Q(n/4)$ ⇒ $O(\sqrt n)$ (Master, $\log_4 2=\frac12$). Vier Randstrecken ⇒ $O(\sqrt n)$, plus $O(R)$ für komplett enthaltene Teilbäume. → 4.3

Was ist ein Range-Tree? Speicher, Aufbau, Anfrage?

Balancierter Baum über $x$; jeder innere Knoten hat einen assoziierten $y$-Baum über seiner kanonischen Teilmenge. Anfrage: 1d-Suche in $x$ liefert $O(\log n)$ kanonische Teilmengen, in jeder 1d-Suche in $y$: $O(\log^2 n+R)$. Speicher $O(n\log n)$ (jeder Punkt in $O(\log n)$ assoziierten Bäumen, einem pro Ebene), Aufbau $O(n\log n)$ durch Mischen von unten. $k$d: $O(n\log^{k-1}n)$ Speicher, $O(\log^k n+R)$ Anfrage. Mit Fractional Cascading ein $\log$ weniger. → 4.4

kd-Baum oder Range-Tree – wann was?

kd-Baum: linearer Speicher, einfach, auch für Nächste-Nachbarn, aber $O(\sqrt n+R)$ (in hohen Dimensionen fast linear). Range-Tree: viel schnellere Anfragen $O(\log^2 n+R)$, aber $O(n\log n)$ Speicher. Viele Anfragen + Speicher egal → Range-Tree. → Vergleich

Kapitel 5 – Voronoi & Delaunay

Definieren Sie das Voronoi-Diagramm. Warum sind die Zellen konvex?

$V(p_i)=\{q : d(q,p_i)<d(q,p_j)\ \forall j\ne i\}$. Jede Zelle ist der Schnitt der $n-1$ offenen Halbebenen $h(p_i,p_j)$ (Seite der Mittelsenkrechten mit $p_i$), und Schnitte konvexer Mengen sind konvex. → 5.1

Zeigen Sie: höchstens 2n−5 Knoten und 3n−6 Kanten.

Knoten $v_\infty$ für die Halbgeraden hinzufügen → zusammenhängender planarer Graph. Euler: $(n_v+1)-n_e+n=2$. Jeder Knoten hat Grad $\ge3$: $2n_e\ge3(n_v+1)$. Einsetzen ergibt $n_e\le3n-6$ und $n_v\le2n-5$. → Satz 2

Was ist die Strandlinie bei Fortune und warum braucht man sie?

Bei Voronoi ist der Bereich direkt über der Sweep-Line noch nicht fertig (ein Punkt unter $\ell$ kann ihn noch beeinflussen). Fertig ist alles über der Strandlinie = untere Einhüllende der Parabeln mit Brennpunkt $p_i$ und Leitlinie $\ell$. Die Knicke laufen entlang der Voronoi-Kanten. → 5.2

Welche Ereignisse gibt es bei Fortune? Was passiert jeweils?

Punktereignis: $\ell$ erreicht einen Site → neuer Bogen spaltet den Bogen darüber, neue Kante beginnt, Kreisereignisse der neuen Tripel prüfen, ein evtl. vorhandenes Kreisereignis des gespaltenen Bogens löschen (false alarm). Kreisereignis: $\ell$ erreicht den tiefsten Punkt eines leeren Kreises durch drei benachbarte Bogen-Sites → mittlerer Bogen verschwindet, Kreismittelpunkt wird Voronoi-Knoten, neue Kante beginnt, neue Tripel prüfen. → 5.2

Warum läuft Fortune in O(n log n) und warum ist das optimal?

$n$ Punktereignisse, $\le 2n-5$ Kreisereignisse, je konstant viele Operationen à $O(\log n)$ auf $Q$ und $T$. Speicher $O(n)$ (höchstens $2n-1$ Bögen). Optimal: Aus dem Voronoi-Diagramm bekommt man die konvexe Hülle in $O(n)$ (unbeschränkte Zellen im Kreis ablaufen), die braucht $\Omega(n\log n)$. → Satz 7

Was ist die Delaunay-Triangulierung? Welche Eigenschaften hat sie?

Der duale Graph des Voronoi-Diagramms (Kante zwischen $p_i,p_j$, wenn ihre Zellen eine Kante teilen). Bei höchstens drei Punkten auf einem Kreis eine Triangulierung. Delaunay-Bedingung: Der Umkreis jedes Dreiecks ist leer (Satz 8). Max-Min-Winkel: maximiert den kleinsten Winkel (Satz 9). Rand = konvexe Hülle, enthält EMST und nächste Nachbarn. → 5.3

Beweisen Sie den Max-Min-Winkel-Satz (Idee).

Illegale Kante (gegenüberliegender Punkt im Umkreis) → Viereck ist konvex → Flip. Nach dem Peripheriewinkelsatz wird der kleinste der sechs Winkel dabei größer, der sortierte Winkelvektor lexikographisch größer. Endlich viele Triangulierungen ⇒ die beste hat keine illegale Kante ⇒ ist Delaunay. → Satz 9

Erklären Sie den randomisierten inkrementellen Delaunay-Algorithmus.

Hülle (oder Super-Dreieck), dann Punkte in zufälliger Reihenfolge einfügen: Dreieck mit $p_r$ finden, alle Dreiecke mit $p_r$ im Umkreis entfernen (zusammenhängend, BFS über Nachbarn), das sternförmige Loch mit $p_r$ fächern. Korrekt nach Satz 11. Naiv $O(n^2)$, mit Point-Location erwartet $O(n\log n)$, weil pro Schritt erwartet $\le6$ Dreiecke geändert werden (Rückwärtsanalyse: Durchschnittsgrad $<6$). Speicher $O(n)$. → 5.4

Warum braucht man die zufällige Reihenfolge?

Die $\le6$ Änderungen gelten nur im Erwartungswert über die Reihenfolge. Bei einer ungünstigen festen Reihenfolge kann jedes Einfügen $\Theta(r)$ Dreiecke betreffen ⇒ $\Theta(n^2)$. Zufall macht das unabhängig von der Eingabe (kein „böser“ Input mehr, nur Pech mit kleiner Wahrscheinlichkeit). → 5.4

Querschnittsfragen

Welche Algorithmen der Vorlesung sind Sweep-Line-Algorithmen? Was ist bei jedem die Ereignis- und die Statusstruktur?

Algorithmus	Ereignisse	Status
Graham's Scan (als Sweep gelesen)	Punkte nach $x$	Stack der Hülle
Iso-orientierte Segmente	Endpunkte, Vertikale	$y$-Werte der aktiven Horizontalen
Bentley–Ottmann	Endpunkte + Schnittpunkte	aktive Segmente sortiert nach $y$
Fortune	Sites + Kreisereignisse	Strandlinie (Bögen)

Wo taucht Ω(n log n) überall auf, und wie zeigt man es?

Konvexe Hülle (Reduktion Sortieren → Parabel), Voronoi (Reduktion Hülle → Voronoi), Delaunay (ebenso, Rand = Hülle). Immer per Reduktion von einem Problem mit bekannter unterer Schranke in $O(n)$.

Was bedeutet „ausgabesensitiv“? Beispiele?

Laufzeit hängt auch von der Größe der Ausgabe ab. Jarvis $O(nh)$, Chan $O(n\log h)$, iso-orientierte Segmente $O(n\log n+R)$, Bentley–Ottmann $O((n+k)\log n)$, kd-Baum $O(\sqrt n+R)$, Range-Tree $O(\log^2n+R)$.

Was ist „allgemeine Lage“ und wie geht man in der Praxis damit um?

Annahme, dass keine Degenerationen vorkommen (kollinear, gleiche Koordinaten, kozirkulär). Vereinfacht Algorithmen und Beweise. In der Praxis: Sonderfälle explizit behandeln, lexikographische Ordnung statt nur $x$, symbolische Perturbation (Simulation of Simplicity), exakte Prädikate.