Kurs 1840 Algorithmische Geometrie

13.9.2000

Prüfer: Prof. Klein

Note: 1.0

Dauer 25 min.

1. (malt eine Punktmenge) zeichnen Sie bitte die konvexe Hülle ein. Wie ist sie definiert?
   • die konvexe Hülle ist die kleinste konvexe Obermenge
   • eine Menge ist konvex, wenn sie jedes Liniensegment, welches zwei ihrer Punkte verbindet enthält.
   • ausserdem wissen wir, dass Die konvexe Hülle alle Punkte der Menge S entweder im Inneren oder auf dem Rand enthält.
2. Wie kann man die konvexe Hülle berechnen?
   • z.B. durch Sweep, erfordert jedoch vorheriges Sortieren der Punkte nach einer Koordinate.
   • Dann können wir die konvexe Hülle über das Konturpolygon (am Beispiel eingezeichnet) in linearer Zeit konstruieren (erklärt, warum bei der Berechnung der konvexen Hülle trotz Rücksprüngen auf den Kanten nur O(n) Punkte betrachtet werden müssen).
   • Daran sieht man, dass die Berechnung der konvexen Hülle genauso schwierig ist, wie das Sortieren und umgekehrt.
3. Dass man auch umgekehrt eine Sortierung aus der konvexen Hülle herleiten kann, sieht man hier aber nicht!
   • Beispiel mit Punkten auf einer Parabel gezeichnet, wenn die konvexe Hülle bekannt ist, können die Punkte in linearer Zeit sortiert berichtet werden.
4. Dass man in einem konvexen Polygon von jedem Punkt aus das gesamte Polygon sehen kann, glauben Sie mir sicher, aber warum ist das so?
   • (Zuerst versucht kompliziert über den Kern des Polygons und die entsprechenden Halbebenenschnitte zu begründen, bis mir die von mir bereits erwähnte Definition einer konvexen Menge einfiel) Wenn ein konvexes Polygon jedes Liniensegment zwischen zwei Punkten enthält, dann muss man auch von jedem Punkt aus jeden anderen sehen können.
5. Sie hatten bereits den Kern eines Polygons angesprochen. Wie bestimmt man ihn?
   • Er wird durch den Schnitt aller linker Halbebenen gebildet, die entstehen, wenn man die Polygonkanten gegen den Uhrzeigersinn abläuft.
   • Somit kann man ihn auf jeden Fall in O(n log n) berechnen.
6. Warum O(n log n)?
   • Weil wir die Berechnung von n Halbebenenschnitten auf die Berechnung der konvexen Hülle ihrer dualen Punkte zurückführen können.
7. Geht es auch besser?
   • Ja, indem wir nur die wesentlichen Kanten betrachten. Hierzu bilden wir die Mengen F und B, die jeweils die Kanten enthalten, die sich weiter nach links (bzw. rechts) drehen, als das bisherige Maximum. Dadurch erhalten wir bereits eine Sortierung und können den Kern in O(n) berichten.
8. Wenn man den gesamten Rand eines einfachen Polygons gesehen hat, hat man dann auch das ganze Polygon gesehen?
   • Ja, denn ein Punkt im Polygon, den wir noch nicht gesehen haben könnte sich höchstens hinter einer Spitzen Ecke befinden, wenn wir aber den gesamten Rand gesehen haben, haben wir auch die abgewandte Kante der spitzen Ecke gesehen und somit auch den Punkt.
9. Und wenn ich Löcher im Polygon erlaube?
   • Ich hatte 'ja' gesagt, da ich von einer Reise entlang aller Polygonkanten, also auch dem kompletten Rand der Löcher ausgegangen war, Prof. Klein zeichnete jedoch eine Konstruktion aus vier schmalen Rechtecken, die zusammen ein Quadrat mit "Gucklöchern" bilden. Hier kann man auf der Rundreise gerade alle Kanten gesehen haben, im Inneren des Quadrats könnte sich jedoch trotzdem ein Punkt versteckt haben. Diese Frage war jedoch ohne Einfluss auf die Benotung.
10. (Zeichnet vier Punkte) Bilden sie hierzu bitte das Voronoi-Diagramm, wie ist es definiert?
    • Die Voronoi-Region eines Punktes p enthält genau die Punkte, die als nächsten Nachbarn p haben.
    • Entfernt man diese, bleiben genau das Voronoi-Diagramm, es enthält alle Punkte, die zwei oder mehr nächste Nachbarn haben.
11. Inwiefern hängt das Voronoi-Diagramm mit der konvexen Hülle zusammen?
    • Ich kann die konvexe Hülle in linearer Zeit berichten, indem ich alle unbeschränkten Voronoi-Regionen betrachte. Ihre Punkte bilden genau die konvexe Hülle.
12. Warum ist das so?
    • Wenn ich einen Kreis mit Mittelpunkt auf der Voronoi-Kante durch p und q ziehe und den Mittelpunkt nach aussen schiebe, nähert er sich der äusseren Halbebene von p und q an. Würde er irgendwann auf einen anderen Punkt treffen, der p und/oder q die Zugehörigkeit an der konvexen Hülle streitig machen könnte, dann würde der Mittelpunkt des Kreises einen Voronoi-Knoten markieren, was der Unbeschränktheit der Region widerspräche.
13. Wie kann man effizient bestimmen, in welche Voronoi-Region ein beliebiger Punkt gehört?
    • Man teilt das Diagramm horizontal in Streifen durch alle Knoten. Aus diesen kann man in O(log n) den richtigen herausfinden.
    • Innerhalb des Streifens kann man wieder in O(log n) die entsprechende Region herausfinden, da innerhalb des Streifens nur noch ein eindimensionales Problem existiert. (Es kann durch die Konstruktion keine Knoten innerhalb des Streifens mehr geben.)
14. Wo ist der Pferdefuss an diesem Algorithmus?
    • Er kann quadratischen Speicher benötigen, da jede Region in beliebig vielen Streifen vorkommen kann.

Dies war meine zweite Prüfung bei Prof. Klein und ich hatte mich schon regelrecht auf die Prüfung gefreut, da Prof. Klein (wie aus allen übrigen Protokollen bekannt) einen sehr angenehmen Prüfungsstil besitzt und den Prüfling zu keinem Zeitpunkt unter Druck setzt, sondern im Gegenteil bei Hängern wohlwollend anschiebt.
Wie wohlwollend die Benotung ist, zeigt die Tatsache, dass ich bei drei Fragen nur mit viel Hilfe auf den richtigen Weg kam und bei den letzten beiden Fragen über die Streifenmethode im Voronoi-Diagramm nur wenig sinnvolles beizutragen hatte.