Topic outline

  • General

    • Kursbeschreibung

      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. Wir werden Techniken und Konzepte behandeln, die für den Entwurf und die Analyse geometrischer Algorithmen und Datenstrukturen benötigt werden. Jede Technik und jedes Konzept wird anhand eines konkreten Problems illustriert, das sich aus einem der oben genannten Anwendungsbereiche ergibt.

      Am Ende dieses Kurses sollen die TeilnehmerInnen in der Lage sein, für einfache geometrische Problemstellungen eigene effiziente Lösungen zu entwickeln. Dazu sollen sie grundlegende Algorithmen und Datenstrukturen, sowie Entwurfs- und Analysetechniken kennen lernen und anwenden können.

      Vorlesungen:
      Die Vorlesungen werden als Videos zur Verfügung gestellt.
      Zum Vorlesungstermin (Montag, 16:00 Uhr) finden Frage- und Diskussionsrunden per Zoom statt.
      Der Meeting Link ist ganz oben auf der WueCampus Seite zu finden (nur angemeldet sichtbar).

      Übungen:
      Donnerstag, 14:15 - 15:45 Uhr (erstmalig Do, 28. Oktober).
      Ob die Übungen per Zoom oder in Präsenz stattfinden wird noch per Umfrage festgelegt.

      Dozenten:
      Boris Klemz (Vorlesungen), Johannes Zink (Übungen)

      Prüfung:
      Termin und Form der Prüfung werden noch bekannt gegeben.
      Ein Bonus von 0,3 auf die finale Note wird an Studierende vergeben, die mindestens 50% der Punkte auf den Übungsblättern erreichen und die Prüfung bestehen.

      Umfang
      5 ECTS (2+2 SWS)

      Modul:
      Algorithmische Geometrie

      Vorraussetzung:   
      Sehr empfohlen: Algorithmen und Datenstrukturen (Bachelor Informatik) oder Vergleichbares

      Zielgruppe: Master Informatik, Master Mathematik, Master Computational Mathematics, Bachelor Games Engineering

       Anmeldung: Für die Teilnahme an der Prüfung ist eine rechtzeitige Anmeldung in WueStudy erforderlich.
      Zusätzlich ist eine Anmeldung in WueCampus nötig, um auf das Lehrmaterial zugreifen zu können (oben links auf die weißen Zahnräder auf blauem Grund und dann auf "Mich in diesem Kurs einschreiben" klicken).


    • Literatur und zusätzliche Materialien

      • 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)
      • Computational Geometry: An Introduction Through Randomized Algorithms.
        Ketan Mulmuley. Prentice Hall, 1st edition, 1993.