Mögliche Prüfungsfragen zum Kurs 1840: Algorithmische Geometrie

Zu Kurseinheit 1:

• Wie lautet die Eulersche Formel für kreuzungsfreie geometrische Graphen in der Ebene? Beweis?
• Was bedeutet es, daß die Laufzeit eines Algorithmus in O(f(n)) bzw. \Omega(f(n)) liegt?
• Was versteht man unter einer Zusammenhangskomponente einer Menge?
• Warum benötigt der Elementtest bei einer Menge mit m Zusammenhangskomponenten im linearen Modell mindestens \Omega(log m) Zeit?
• Wie kann man aus der vorigen Frage schließen, daß die Bestimmung des kleinsten Abstands zwischen n Punkten in der Ebene mindestens \Omega(n log n) Zeit braucht?

Zu Kurseinheit 2:

• Wie würden Sie durch Sweep das zweitgrößte Element in einer Folge von n Zahlen bestimmen? Das drittgrößte? Das k-t-größte? Welche SSS würden Sie dabei benutzen, und wie hinge die Laufzeit dann von n und k ab?
• Erläutern Sie das Sweep-Verfahren für die Bestimmung des dichtesten Paars von n Punkten in der Ebene. Warum
  • genügt es,
  • ist es für die Laufzeit wichtig,
  daß man sich während des sweeps nur die Punkte im vertikalen Streifen links von der sweep line merkt?
• Wie würden Sie die Schnittpunkte von n nicht-senkrechten Geraden berechnen?
• Aus wievielen Segmenten kann die untere Kontur von n Parabeln bestehen, deren Mittelachsen senkrecht sind und die sich nach oben öffnen?
  Wie würden Sie diese untere Kontur effizient berechnen?
• Zu jeder endlichen Punktmenge existiert ein einfaches Polygon, das jeden Punkt aus der Menge als Eckpunkt besitzt. Wie kann man durch einen Sweep ein solches Polygon berechnen, wie hoch ist der Aufwand?

Zu Kurseinheit 3:

• Was versteht man unter einer zerlegbaren Anfrage?
• Wie läßt sich bei einer rein statischen Struktur für zerlegbare Anfragen die Operation Einfügen so implementieren, daß die amortisierten Kosten gering sind?
• Gegeben ist ein Datentyp zur Speicherung von Objekten einer geordneten Grundmenge mit den Operationen Aufbau, Löschen, Entfernen, Bericht des Minimums.
  • Welche Datenstruktur würden Sie benutzen, um das Entfernen schwach zu implementieren?
    (Hinweis: Kann man die Vorzüge von sortierten Arrays und von Listen miteinander verbinden?)
  • Welche Laufzeiten ergeben sich, wenn man das Entfernen dynamisiert?
• Konstruieren Sie einen 2-d-Baum aus einer gegebenen Punktmenge, und beschreiben Sie die Beantwortung von Bereichsanfragen.

Zu Kurseinheit 4:

• Beschreiben Sie einen O(n log n) Algorithmus zur Konstruktion der konvexen Hülle von n Punkten in der Ebene, und begründen Sie sein Laufzeitverhalten.
• Beschreiben Sie Graham's scan zur Berechnung der konvexen Hülle von n Punkten in der Ebene und schätzen Sie die Laufzeit ab.
• Ein Kreis enthalte eine Ellipse. Wer von beiden hat den längeren Umfang?
• Kann es in einem einfachen Polygon zwei Punkte p,q geben, die dasselbe Sichtbarkeitspolygon haben? Wenn ja, können p und q sich sehen?
• Bestimmen Sie den Kern eines Beispielpolygons nach dem im Kurs angegebenen Verfahren. Wieviel Zeit benötigen Sie?
• Wenn Sie ein Polygon durchlaufen und den gesamten Rand gesehen haben, haben Sie dann bereits das gesamte Polygon gesehen? Beweisen Sie Ihre Aussage.

Zu Kurseinheit 5:

• Zeichnen Sie das Voronoi-Diagramm zu vier oder fünf vorgegebenen Punkten (euklidisch).
• Für welche Punktmengen hat das Euklidische Voronoi-Diagramm die Struktur eines Baumes?
• Warum ist der nächste Nachbar eines Punktes p in S stets ein Voronoi-Nachbar in V(S)?
• Kann es fünf Punkte in der Ebene geben, so daß jede Voronoi- Region zu jeder anderen benachbart ist? (Hinweis: Denken Sie an den Graphen K_5 aus der Aufgabe 1.3)
• Wie sehen die Einheitskreise der L_1 und L_\infty ("L-unendlich") aus? Angenommen, Sie haben einen Algorithmus zur Berechnung von L_1-Diagrammen. Können Sie ihn auch bei der Berechnung von L_\infty-Diagrammen benutzen?
• Wie kann man die Bisektoren von zwei Punkten bezüglich einer konvexen Distanzfunktion bestimmen?

Zu Kurseinheit 6:

• Beschreiben Sie eines der Verfahren
  • Inkrementelle Konstruktion
  • Sweep
  • Divide and Conquer
  zur Berechnung des Voronoi-Digrammes und skizzieren Sie die jeweilige Laufzeitabschätzung.
• Was versteht man im Sweep-Verfahren unter der Wellenfront? Wie ist ihre Komplexität und ihre Struktur?
• Wie findet man beim Verfahren Divide and Conquer die Endstücke von B(L,R)?
• Was ist ein Konfliktdreieck bezüglich eines Knotens p_i aus der Delaunay-Triangulierung DT_(i-1)? Wie groß ist die Anzahl der Konfliktdreiecke eines Knotens in bezug auf den Grad des Knotens in DT_i?

Zu Kurseinheit 7:

• Wie findet der Pledge-Algorithmus aus den Windungen eines spiralförmigen Hindernisses heraus? (Am Beispiel demonstrieren)
• Ist es möglich, daß der Pledge-Algorithmus eine Kante beliebig oft besucht? Beweisen Sie Ihre Aussage.
• Angenommen, Sie wissen, daß die Tür in der Wand genau den Abstand k von Ihrer Startposition hat, aber nicht, auf welcher Seite sie liegt. Welchen kompetitiven Faktor können Sie erreichen?
• Beschreiben Sie allgemein das Verfahren zur Suche nach einem Zielpunkt in einem einfachen Polygon (mit Sichtsystem).
• Sei P ein einfaches Polygon und p ein Punkt in P. Wann gilt: p liegt auf dem Rand des Kerns des Sichtbarkeitspolygons von p?
• Skizzieren Sie kurz die Idee der Suchstrategie der m Halbgeraden. Welche Eigenschaft der geometrischen Reihe macht man sich generell zunutze?