Gedächtnisprotokoll zur Diplomprüfung
Vertiefende Kurse der Informatik

• Wie bestimmt man naiv das kleinste Punktepaar einer Menge von Punkten?
  • Durch paarweises Vergleichen.
• Laufzeit?
  • O(n^2)
• Und mit Hilfe eines besseren Algorithmus?
  • Sweep-Verfahren erklären.
• Laufzeit?
  • O(n log n)

• Voronoi-Diagramm eignet sich auch dafür. Aufmalen eines Voronoi-Diagramms von 4 Punkten.
• Wie kann man das kleinste Punktepaar mit dem Voronoi-Diagramm finden?
  • Nächste Nachbarn eines Punktes haben benachbarte Voronoi-Regionen. Suchen des Minimums unter allen Nachbarn.
  • Laufzeit bei existierendem Voronoi-Diagramm: O(n), denn es gibt nur O(n) Voronoi-Kanten.
• Warum gibt es nur O(n) Voronoi-Kanten?

• Was kann man noch mit einem Voronoi-Diagramm machen?
  • Konvexe Hülle einer Punktmenge bestimmen.
• Beschreibung eines Verfahrens zur Konstruktion des Voronoi-Diagramms (man darf sich eins aussuchen).
• Zeitbedarf?
  • O(n log n).
• Geht es noch schneller?
  • Nein.
• Warum nicht?
  • Weil sich aus Voronoi-Diagramm in linearer Zeit die konvexe Hülle herleiten läßt, und die durch Bestimmung der konvexen Hülle in linearer Zeit eine Menge von Punkten sortiert werden kann, und das Sortieren \Omega(n log n) dauert. (Dies ist die "lange" Erklärung, es geht auch kürzer)

• Bestimmung des Kerns eines Polygons. Zuerst zeichnerisch. Danach Algorithmus erklären: Durchschnitt der inneren Halbebenen. Dies hat Laufzeit O(n log n). Mit Bestimmung der wesentlichen Kanten (B- und F-Menge, siehe Kapitel 4.4) geht dies in linearer Laufzeit.

Die Prüfung verlief sehr nett und ruhig. Wenn man etwas nicht weiß, wird man nicht lange "gequält", sondern bekommt zuerst ein oder zwei Hilfestellungen, und kurz danach beantwortet Prof. Klein selbst die Frage.