Link zum Vorlesungsverzeichnis.
Neben den angegebenen Teilen des Buchs sollten alle Vortragenden Abschnitt 1.2.4 zur Komplexitätstheorie gelesen haben.
Termin | Vortrag/Inhalt | Quelle | Vortragende |
---|---|---|---|
16. 04. | Organisatorisches Treffen |
||
23. 04. | 1D Sweep-Verfahren: Grundlagen und dichtestes Zahlenpaar Dieser Vortrag beschäftigt sich mit dem Finden des minimalen Abstands von zwei Elementen einer Menge von reellen Zahlen. Das schnellstmögliche Lösen dieses Problems führt auf ein eindimensionales Sweep-Verfahren, dessen Optimalität mithilfe des Problems ε-closeness gezeigt wird. |
1.2.5, 2.1, 2.2 | Sebastian Manecke |
30. 04. | 2D Sweep-Verfahren: Dichtestes Punktpaar in der Ebene | 2.3.1 | Paul Schmitz-Moormann |
14. 05. | 2D
Sweep-Verfahren: Schnittpunkte von Liniensegmenten Dieser Vortrag beschäftigt sich mit dem Problem des Findens von Schnittpunkten einer Menge von Liniensegmenten. Hierbei ist sowohl die einfachere Frage, ob ein Schnittpunkt existiert, als auch, wie viele / welche Schnittpunkte es gibt, interessant. |
2.3.2 | Amina Felic |
21. 05. | 2D Sweep-Verfahren:
Untere Konturlinien von Funktionen In diesem Vortrag wird das Problem der unteren Konturlinien von Funktionen behandelt. Auch hier wird sich ein Sweep-Algorithmus als nützlich erweisen, welcher jedoch mit einem divide-and-conquer-Verfahren kombiniert wird. Die Laufzeitanalyse des Verfahrens führt überraschend zu einem kombinatorischen Problem, nämlich das Bestimmen von maximalen Längen von Davenport-Schinzel-Sequenzen. |
2.3.3 | Marlene Eichholtz |
04. 06. | 2D Sweep-Verfahren:
Schnitte von Polygonen Ein in der Praxis sehr relevantes Problem ist das Bestimmen der Überschneidung von zwei Polygonen. Dieser Vortrag baut auf den Schnittpunktbestimmungen im dritten Vortrag auf und erweitert das Verfahren zur Lösung dieses Problems. |
2.3.4 | Jonas Strauch |
11. 06. & 18. 06. |
Konvexe Hüllen von Punktmengen: Teil 1 und Teil 2 Das Bestimmen der konvexen Hülle einer Punktmenge ist auch ein sehr klassisches Problem der algorithmischen Geometrie. Hier soll aufbauend auf dem vierten Vortrag ein Verfahren vorgestellt werden, welches die untere und obere Konturlinie des entstehenden Polygons entlangläuft. Ein duales Problem dazu, das Bestimmen des Schnitts von Halbräumen, soll ebenfalls behandelt werden. |
4.1.1, 4.1.3, 4.1.4 | Philippe Lerch & Robin Dass |
25. 06. | Triangulierungen und das
Museumswächterproblem Beim Museumswächterproblem versucht man mit möglichst wenig Wächtern ein Museum (modelliert als Polygon) vollständig zu überwachen. Dies führt zum Problem der Zerlegung des Problems in Dreiecke, für welches ein Algorithmus betrachtet werden soll. |
4.2, 4.3.3 | Raely Wersdörfer Ferreira |
02. 07. & 09. 07. |
Anwendungen von
Voronoidiagrammen
Das "Nächstes-Postamt"-Problem, die Bestimmung aller nächsten Nachbarn, die Erstellung eines minimalen aufspannenden Baumes und das finden eines Ortes ist, der maximal von Störquellen entfernt ist, sind nur einige Anwendungen von Voronoidiagrammen. Diese und andere zentrale Eigenschaften eines Voronoidiagramms sollen in diesem Vortrag behandelt werden. |
5.1 - 5.3 | Pascal Neukirchner & Tim Kaufmann |
16. 07. | Delaunay Unterteilung
Dual zu den Voronoidiagrammen haben auch die Delaunay-Unterteilungen viele nützliche Eigenschaften. Beispielsweise maximieren sie den kleinsten Winkel unter allen Triangulierungen, was für numerische Berechnungen wichtig ist. Diese Aussage lässt sich auf elementargeometrische Betrachtungen zurückführen. |
5.4 | Luca Iffland |