Thema

Die Algorithmische Geometrie (engl. Computational Geometry) beschäftigt sich mit algorithmischen Fragestellungen, bei denen die Ein- und/oder Ausgabedaten geometrische Objekte sind, also Punkte, Strecken, Geraden, Ebenen, Kreise, Polygone, usw. Derartige Probleme spielen in vielen Bereichen der Informatik, bei denen es notwendig ist räumliche Daten zu speichern, zu analysieren, zu erzeugen oder zu manipulieren, eine Rolle; dazu gehören beispielsweise Robotik, Geografische Informationssysteme (GIS), CAD/CAM, Computergrafik und Virtual Reality. Zu diesem Thema wird an unserem Lehrstuhl auch jedes Jahr im Winter eine Vorlesung angeboten.

In diesem Seminar wollen wir uns mit aktuellen Forschungsthemen der Algorithmische Geometrie beschäftigen. Dabei werden insbesondere Themen behandelt, die erst vor Kurzem auf dem 38th European Workshop on Computational Geometry (EuroCG) im März 2022 vorgestellt wurden. Im Seminar kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen, sowie Algorithmische Graphentheorie zum Einsatz. Die Vorlesung Algorithmische Geometrie gehört zu haben ist hilfreich, aber nicht erforderlich. Manche Themen enthalten spannende offene Forschungsfragen. Wenn in der zweiten Hälfte des Seminars Zeit bleibt, kann daran gemeinsam geforscht werden. Außerdem können sich dadurch Themen für Praktika oder Abschlussarbeiten im Anschluss an das Seminar ergeben.

Fast allen Themen liegt ein aktueller EuroCG Artikel zugrunde - diese können im Tagungsband der EuroCG (Achtung: Dateigröße 38MB) unter der jeweiligen Artikelnummer gefunden werden. Dabei handelt es sich jeweils um einen Abstract, also eine Kurzfassung eines längeren Artikels - diese Vollversionen sind jeweils neben den Themen verlinkt. Bei einigen Themen haben wir außerdem einen Hauptartikel aufgeführt. Bei diesen Themen sollen sich die Vorträge und Ausarbeitungen hauptsächlich auf diesen Artikel konzentrieren, der in der Regel weitaus grundlegender ist, als der angegebene EuroCG Beitrag. Auf Letzten soll in diesem Fall nur kurz eingegangen werden. Die meisten Artikel sollten, zumindest aus dem Uninetz / per VPN, frei verfügbar sein. Falls der Zugriff nicht klappt, meldet euch einfach bei uns.

Lernziele

Ziel ist es, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen KursteilnehmerInnen in einem Vortrag, sowie in einer schriftlichen Ausarbeitung zu vermitteln. Für jedes Thema geben wir einen Artikel bzw. ein Buchkapitel vor. Sie sollen aber auch noch selbst Literaturrecherche betreiben. Ein Ausgangspunkt dafür können beispielsweise die Referenzen in Ihrem Artikel sein. Da wir das Seminar auf die aktuelle Forschung hin ausrichten wollen, sind insbesondere offene Forschungsfragen ein wichtiger Bestandteil der Themen.

Sie bekommen im Seminar einen Überblick über Techniken, sowie Modellierungs- und Lösungsansätze der Algorithmischen Geometrie. Dieses Thema eignet sich übrigens auch gut für Abschlussarbeiten.

Ablauf

• Im ersten Treffen werden wir den Ablauf des Seminars besprechen und die Themenverteilung festlegen.
• Im zweiten Treffen geben alle TeilnehmerInnen einen kurzen Überblick über ihr Thema (max. 5 Minuten, ca. 3 Folien).
• In den folgenden Treffen finden die eigentlichen Vorträge der TeilnehmerInnen statt. Neben dem Vortrag bleibt auch Zeit zur Diskussion der Themen und daraus resultierender offener Fragen für die weitere Forschung.
• Die Ausarbeitungen sind zum Ende der Vorlesungszeit anzufertigen.

Module

Bei erfolgreicher Teilnahme wird die Leistung als (benotetes) Seminar für den Bachelor- oder Masterstudiengang Informatik eingetragen.

Allgemeine Literatur zur Algorithmischen Geometrie

• Computational Geometry: Algorithms and Applications.
  Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars.  Springer-Verlag, 3rd edition, 2008.
  [ Online verfügbar ] (Mit Uni Account)
  
• Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen.
  Rolf Klein. Springer-Verlag, 2nd edition, 2005.
  [ Online verfügbar ] (Aus dem Uni Netz)