Prüfungsprotokoll Diplomprüfung Algorithmische Geometrie

Fangen wir doch mal mit dem dichtesten Paar an...

In welcher Dimension?

Erst mal im Eindimensionalen – wie würden Sie das machen?

Hmm – erst mal sortieren und dann das Minimum berechnen

Okay – und im Zweidimensionalen?

Habe den Sweep erklärt und wurde ziemlich detailliert nach der Realisierung der SSS gefragt und musste ziemlich genau sagen, warum die Laufzeit denn jetzt O(n log n) ist.

Gut – und wie ist es im R³?

Hier bin ich kurz auf die sweep plane eingegangen und habe gesagt, dass die Bereichsabfrage hier in einer zweidimensionalen Struktur stattfindet und dass deshalb das Laufzeitverhalten auch mit O(n (e(n)+b(n)) von der Realisierung dieser Struktur abhängt.

Anderes Thema – er malte 4 Punkte auf und ich sollte das Voronoi-Diagramm zeichnen. Erklären Sie mal genau, was ein Voronoi-Diagramm ist.

Habe erklärt, dass die Regionen durch den Schnitt von n-1 Halbebenen entstehen und einige Eigenschaften des Diagramms erklärt. Voronoi-Kante und Voronoi-Knoten

Malen Sie jetzt mal den dualen Graphen – was ist das dann?

Die Delaunay-Triangulation.

Welche Eigenschaften hat die denn jetzt?

Größte Winkelfolge – musste ich genauer erklären. Größter leerer Kreis.

Was kann man denn mit so einem Voronoi-Diagramm oder der Delaunay-Triangulation genau machen?

Mir fielen auf Anhieb nur dichteste Abstände zu allen Punkten und die konvexe Hülle ein. Das musste ich dann auch genau erklären und habe das mit dem Kreis dessen Mittelpunkt immer weiter nach außen wandert zwar nicht gut gemalt aber wohl ausreichend erklärt.

Wie ist das jetzt mit dem größten Kreis?

Habe versucht eine willkürliches konvexes Polygon über das Voronoi-Diagramm zu machen und habe erklärt, wo sich der Mittelpunkt nur befinden kann und wie man jetzt herausbekommt, wo die Schnittpunkte sind und warum das genau in O(n+m) Zeit funktioniert.

Dann ging er zu einer langen Wand mit einem Roboter, der nur mit dem Tastsensor ausgestattet ist, über

Habe erklärt, wie das mit der Suchtiefenverdoppelung pro Schritt ist und wie man damit auf einen kompetitiven Faktor von 9 kommt.

Was genau ist ein kompetitiver Faktor?

Habe K_S(P)£C*K_opt(P)+A

Gibt es einen besseren als 9?

Wusste ich nicht, hab aber mal nein geschätzt – ohne Beweis. Es stimmte, er meinte aber auch, dass der Beweis ziemlich lang war!

Dann hat er ein Polygon aufgemalt – wollte es sternförmig machen – hat auch funktioniert.

Das habe ich erkannt und sagt, dass es sternförmig ist und dass das bedeutet, dass der Kern nicht leer ist.

Dann sollte ich den Kern mal schnell einmalen. Wie lange braucht man dafür?

Erst mal hab ich's normal über den Durchschnitt der Halbebenen gemacht und dann grob den Algorithmus mit Winkelbestimmung, F und B und der Ausnutzung der Dualität zwischen Geraden und Punkten über konvexe Hülle für sortierte Punkte erklärt.

Jetzt stellen Sie sich mal vor, Sie kennen das Polygon noch gar nicht und starten hier – wie gehen sie dann vor?

Habe die Strategie CAB erklärt mit Gewinnbereich.

Wie ist da der kompetitive Faktor?

5,3331 – weil CAB immer selbstnähernde Wege erzeugt.

Angenehme Prüfungsatmosphäre. Dr. Icking wirkt sehr locker und macht es einem dadurch auch etwas leichter reinzukommen. Dr. Icking fragte sofort am Anfang nach einer Kurseinheit, in der ich nicht geprüft werden wollte und fragte, ob mir das klar gewesen sei. Ich war mir vorab nicht so sicher und sagte das auch und daraufhin meinte er, er müsse das wohl etwas offizieller machen – damit es allen Prüflingen von vornherein klar sei. Ich habe – wie die meisten – auch KE3 gewählt.

Viel Erfolg!