Proseminar (BaM-CM)

Diskrete Mathematik / Algorithmische Geometrie

Sommersemester 2019

Prof. Raman Sanyal, Sebastian Manecke



Aktuelles

Was

Das sind typische Fragestellungen der Algorithmischen Geometrie, in die das Proseminar einen ersten Einblick geben soll. Mit Hilfe von Werkzeugen aus der Linearen Algebra und der Computer-orientierten Mathematik (Diskrete Mathematik, einfache Algorithmen/Datenstrukturen) wollen wir das Modellieren und Lösen obiger Probleme mit Blick auf die Effizienz (Laufzeiten) von Verfahren kennenlernen. Als Quellen dienen uns die folgenden beiden als eBook(!) vorhandenen Bücher.

Link zum Vorlesungsverzeichnis.

Wann und wo

Dienstags, 8-10, Robert-Mayer-Str. 10, Raum 711kl

Organisation / Spielregeln

Ziel es Proseminars ist es zu lernen wie ein mathematisches Thema übersichtlich und klar präsentiert wird.

Themen und vorläufige Termine

Die folgende Tabelle gibt einen Überblick über die angebotenen Themen, Inhalte und zugeordnete Termine. Alle Kapitelangaben beziehen sich auf das obige (online-verfügbare!) Buch von Rolf Klein.

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


Impressum    Datenschutzerklärung