Section outline

  • General

    Contreu-ho tot Expandeix-ho tot

  • Seminar: Algorithmische Geometrie

    Umfang:

    5 ECTS, 2 SWS

    Zeit & Ort:

    Dienstags, 16:00–17:30 Uhr, Seminarraum III im Informatikgebäude M2 (erstmalig am 18.04.2023)

    Voraussetzung:  

    		 Im Seminar kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen (Info., Bsc.), sowie Algorithmische Graphentheorie (Info., Bsc.) zum Einsatz, diese besucht zu haben ist deshalb sehr empfohlen. Die Vorlesung Algorithmische Geometrie (Info., Master) gehört zu haben, ist hilfreich, aber nicht erforderlich.

    Zielgruppe:

    Master Informatik (empfohlen), Bachelor Informatik

    Dozenten:

    Boris Klemz und Alexander Wolff

    Wenn Sie am Seminar teilnehmen möchten, kommen Sie zum ersten Termin am Dienstag, den 18.04.2023, um 16:00 Uhr – dieser wie auch die restlichen Termine des Seminars - wird in Präsenzform stattfinden. An diesem Termin bitten wir um vollständige Anwesenheit, da wir den Ablauf des Seminars besprechen und die Themenverteilung festlegen. Die Liste der Themen finden Sie bereits jetzt weiter unten auf dieser Seite. Diese werden je nach Teilnehmerzahl jeweils alleine oder zu zweit bearbeitet. Machen Sie sich schon vorab Gedanken, welche Themen Sie bearbeiten möchten.

    Bitte schreiben Sie sich schon jetzt in diesen Wuecampus-Kurs ein, falls Sie am Seminar teilnehmen wollen. Melden Sie sich dazu bei WueCampus an (das haben Sie wahrscheinlich schon getan) und klicken Sie in der "sekundären Navigationsleiste" (der Bereich unter dem Kurstitel) auf "Mich in diesen Kurs einschreiben").


    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 International Symposium on Computational Geometry (SoCG) und dem 39th European Workshop on Computational Geometry (EuroCG) vorgestellt wurden. Im Seminar kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen, sowie Algorithmische Graphentheorie zum Einsatz, diese besucht zu haben ist deshalb sehr empfohlen.. 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.

    Allen Themen liegt ein aktueller Artikel zu einem Beitrag einer der beiden oben genannten Konferenzen zugrunde. Diese haben wir in der Spalte Referenzen jeweils verlinkt. Da die Länge solcher Artikel strikt begrenzt ist, ist es üblich, zusätzlich eine ungekürzte Version auf einem Preprint-Server zu veröffentlichen. Diese Vollversionen sind ebenfalls verlinkt.

    Titel Autor:innen Referenzen
    Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs
    		 Bringmann, Kisfaludi-Bak, Künnemann, Nusser, Parsaeian
    		 SoCG
    Vollversion
    Long Plane Trees
    		 Cabello, Hoffmann, Klost, Mulzer, Tkadlec
    		 SoCG
    Vollversion
    Hop-Spanners for Geometric Intersection Graphs
    		 Conroy, Toth
    		 SoCG
    Vollversion
    Disjointness Graphs of Short Polygonal Chains
    		 Pach, Tardos, Tóth
    		 SoCG
    Vollversion
    Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles
    		 Chung, Demaine, Hendrickson, Luo
    		 SoCG
    Vollversion
    Maximum overlap area of a convex polyhedron and a convex polygon under translation
    		 Zhu, Jun Kweon
    		 EuroCG
    Vollversion
    Sometimes Two Irrational Guards are Needed
    		 Meijer, Miltzow
    		 EuroCG
    Vollversion
    Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
    		 de Berg, Miltzow, Staals
    		 EuroCG
    Vollversion
    Primal-Dual Cops and Robber★
    		 Tuan Ha, Jungeblut, Ueckerdt
    		 EuroCG
    Vollversion
    Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable
    		 Bhore, Ganian, Khazaliya, Montecchiani, Nöllenburg
    		 EuroCG
    Vollversion
    Crossing Minimization in Time Interval Storylines★
    		 Dobler, Nöllenburg, Stojanovic, Villedieu, Wulms
    		 EuroCG
    Vollversion
    Insertion-Only Dynamic Connectivity in General Disk Graphs
    		 Kaplan, Klost, Knorr, Mulzer, Roditty
    		 EuroCG
    Vollversion
    On the geometric thickness of 2-degenerate graphs
    		 Jain, Ricci, Rollin, Schulz
    		 EuroCG
    Vollversion

    ★ Diese Artikel sind weniger umfangreich als die übrigen Themen. Dies sollte jedoch nicht fälschlicherweise mit weniger Bearbeitungsaufwand gleichgesetzt werden. Wer eines dieser Themen wählt, muss damit rechnen, etwas mehr eigene Literaturrecherche betreiben zu müssen oder einen der ersten Vortragstermine mit weniger Vorbereitungszeit zugewiesen zu bekommen.

    Lernziele

    Ziel ist es, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen Kursteilnehmer:innen 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 wir Tipps zum Anfertigen von Ausarbeitungen.
    • Im dritten Treffen geben alle Teilnehmer:innen einen kurzen Überblick über ihr Thema (max. 5 Minuten, ca. 3 Folien).
    • In den folgenden Treffen finden die eigentlichen Vorträge der Teilnehmer:innen 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)

  • Diskussion

    • Notizen Student folder

  • Ausarbeitungen

    Die Ausarbeitung zu ihrem Thema sollte etwa 10 Seiten (zuzüglich Titelseite) umfassen. Sie soll nicht nur den von uns vorgegebenen Artikel zusammenfassen, sondern auch darüber hinaus gehen. Zum Einen eignet sich dafür das Material, dass sie durch eigene Literaturrecherche gefunden haben. Zum anderen kann man hier auch auf interessante offene Fragen eingehen.

    Die Themen des Seminars sollen nicht für sich alleine stehen, sondern wurden bewusst aus einem bestimmten Gebiet gewählt. Nutzen Sie das in ihrer Ausarbeitung und zeigen Sie Verbindungen zu anderen Vortragsthemen des Seminars auf! Vielleicht können Sie dadurch auch neue Fragestellungen entwickeln, die für die weitere Forschung interessant sind. Damit Sie die Möglichkeit haben Ergebnisse aus den anderen Vorträgen in Ihre Ausarbeitung aufzunehmen, muss diese erst eine Woche nach dem letzten Vortrag abgegeben werden.

    Die Ausarbeitungen sollen mit LaTeX erstellt werden. Wenn Sie noch keine Erfahrung mit LaTeX haben, könnte dieser kostenlose Kurs im Rechenzentrum hilfreich sein.