Abschnittsübersicht

  • Allgemeines

    Alles einklappen Alles aufklappen

  • Seminar: Algorithmische Geometrie

    Umfang:

    5 ECTS, 2 SWS

    Zeit & Ort:

    Dienstags, 14:15-15:45 Uhr, Übungsraum II im Informatikgebäude M2 (erstmalig am 26.04.2022)

    Voraussetzung:  

    		 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.

    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 Di, dem 26.04.2022, um 14:15 Uhr – dieser wie auch das gesamte Seminar wird in Präsenzform stattfinden (sofern es keine anderslautende Regelung gibt). 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 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 auf den blauen Knopf links oben mit den weißen Zahnrädern und dort auf "Mich in diesen Kurs einschreiben". (Entsprechend können Sie sich natürlich auch wieder austragen.)

    • 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.

      Titel AutorInnenReferenzen
      Planarizing Graphs and their Drawings by Vertex Splitting
      		Nickel, Nöllenburg, Sorge, Villedieu, Wu, Wulms
      		EuroCG:14
      Vollversion
      Finding a Battleship of Uncertain Shape
      		 Hainzl, Löffler, Perz, Tkadlec, Wallinger
      		EuroCG:48
      Vollversion
      Flipping Plane Spanning Paths Aichholzer, Knorr, Löffler, Masárová, Mulzer, Obenaus, Paul, Vogtenhuber
      		EuroCG:66
      Vollversion
      Unfolding the Simplex and Orthoplex
      		 Devadoss, Harvey
      		EuroCG:11
      Vollversion
      Approximation of Minimum Convex Partition
      		 Knauer, Spillner / Grelier
      		Hauptartikel
      EuroCG:22
      Vollversion
      Transitions in Dynamic Map Labeling
      		 Depian, Li, Nöllenburg, Wulms
      		EuroCG:39
      Vollversion
      Universal point sets for classes of planar graphs
      		 Gritzmann, Mohar, Pach, Pollack / Felsner, Schrezenmaier, Schröder,Steiner
      		Hauptartikel
      EuroCG:49
      Vollversion
      The complexity of geodesic spanners
      		 de Berg, Staals, van Kreveld
      		EuroCG:16
      Blocking Delaunay triangulations
      		 Aichholzer, Fabila-Monroy, Hackl, van Kreveld, Pilz, Ramos, Vogtenhuber / Aichholzer, Hackl, Löffler, Pilz, Parada, Scheucher, Vogtenhuber
      		Hauptartikel
      EuroCG:9
      Compatible geometric matchings
      		 Aichholzer, Bereg, Dumitrescu, García, Huemer, Hurtado, Kano, Márquez, Rappaport, Smorodinsky, Souvaine, Urrutia, Wood
      		Artikel

      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)

  • Vorträge

    • Ihr Vortrag sollte etwa 45 Minuten (bei Einzelvorträgen) bzw. 60 Minuten (zu zweit) dauern.
    • Wir empfehlen für die Erstellung der Folien das kostenlose Programm ipe (verfügbar für Linux, Windows, Mac). Als Einstieg können Sie gerne einen Blick auf die Folien vom Einführungsvortrag werfen. Die PDF-Datei können Sie mit ipe öffnen und weiterbearbeiten.
    • Im Vortrag sollten auch relevante offene Forschungsfragen nicht zu kurz kommen.
    • Die Folien Ihres Vortrages werden wir anschließend hier für alle TeilnehmerInnen zur Verfügung stellen.

  • 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.

    • LaTeX-Vorlage für die Ausarbeitung (mit Schreibtipps!) Link/URL
    • Beispiel einer unkorrigierten früheren Ausarbeitung Datei
      Nicht verfügbar, außer: Sie sind in Seminarteilnehmer