---

Gedächtnisprotokoll der mündlichen Diplomprüfung 1840 - Algorithmische Geometrie - am
                                                          19. 8. 98 - Note: 1.3

---

• Wie berechnet man die maximale Teilsumme naiv?

Jedes Objekt mit jedem vergleichen.
• Zeit?

O(n^2).
• Wie geht es sonst noch?

Sweep erklären.
• Zeit?

O(n^2).
• Was ist ein Sweep allgemein? Welche Strukturen treten auf?

Erklären mit toten, aktiven, schlafenden Objekten, ES und SSS.
• Durchschnitte von Liniensegmenten?

Sweep erklären.
• Wie sieht die ES, wie die SSS aus?

ES enthält die Schnitt, die Anfangs- und die Endpunkte, die SSS die Liniensegmente.
• Wie werden die Liniensegmente gespeichert.

Es reicht die Angabe einer eindeutigen Identifizierung.
• Welche Zeit?

O((n+k)logn).
• Warum?

Weil die Schnittpunkte berichtet werden müssen.
• Was ist eine konvexe Hülle?

Definition.
• Welches Verfahren?

Linke, rechte Kontur, dann Sweep über einzelne Stücke.
• Welches noch? Darin wird O(nlogn) im Mittel erreicht.

Inkrementelles Verfahren erklären.
• Welche Teilprobleme treten dabei auf?

Punkt innerhalb oder außerhalb des bisherigen Polygons. Erlären mit Sektoren. Tangenten bilden.
• Welche Datenstruktur?

Baum => Binäres Suchen => Zeit O(logn), auch für die Aktualisierung der Eckenverzeichnis
• Wie werden die Tangenten gebildet?

Von Sektorenkante aus auf Rand entlang jede Kante untersuchen.
• Zeit?

O(nlogn).
• Auf dem untersuchten Rand können theoretisch fast alle Punkte liegen. Wieso trotzdem O(nlogn)?

Weil in diesem Fall diese Punkte gelöscht werden. D. h., über alle Punkte betrachtet ergibt sich O(nlogn).
• Was ist ein Voronoi-Diagramm?

Erklärung.
• Zeichnen des Diagramms für vier vorgegebene Punkte.
• Welche Punkte haben unbeschränkte Regionen?

Konvexe Hülle.
• Wieso?

Kreis um zwei Punkte mit unbeschränkter Voronoi-Region und Mittelpunkt auf Bisektor. Kein anderer Punkt darin. Mittelpunkt -> oo - Kreis wird immer größer. Nie ein anderer Punkt darin, d. h. auf dieser Seite.
• Wie Voronoi-Diagramm erstellen?

Inkrementell, sweep, divide and conquer.
• Aussuchen.

Sweep.
• Abgelehnt, weil sweep schon drangewesen.

Divide and conquer. Divide-Schritt erklärt. Zeit: O(logn).
• Was ist B(L;R)? Wie findet man es?

Im übereinandergelegten Voronoi-Diagramm suchen. Zeit: O(n).
• Wie restliche Verbindung?

Erklären beim Zeichnen.
• Zeit?

O(n).
• Insgesamte Zeit?
  O(nlogn).

Die Antworten sind die, die ich hätte geben müssen, und nicht unbedingt die, die ich auch gegeben habe. Professor Klein ist ein sehr verständnisvoller Prüfer, der sich alle Mühe gibt, die Prüfung streßfrei ablaufen zu lassen. Er ist keineswegs daran interessiert, jemanden fertigzumachen.