186.122 Algorithmic Geometry
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2018W, VU, 2.0h, 3.0EC

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

Die Studierenden erwerben ein systematisches Verständnis von Fragestellungen und Lösungsansätzen im Bereich der algorithmischen Geometrie, das auf dem bestehenden Wissen in der Theoretischen Informatik und Algorithmik aufbaut. Nach erfolgreicher Teilnahme an der Lehrveranstaltung können die Studierenden

  • Begriffe, Strukturen und grundlegende Problemdefinitionen aus der Vorlesung erklären;
  • geometrische Algorithmen exemplarisch ausführen, mathematisch präzise analysieren und ihre Eigenschaften beweisen;
  • auswählen, welche Algorithmen und Datenstrukturen zur Lösung eines gegebenen geometrischen Problems geeignet sind und diese ggf. einer konkreten Problemstellung anpassen;
  • unbekannte geometrische Probleme analysieren, auf den algorithmischen Kern reduzieren und daraus ein abstraktes Modell erstellen; auf Basis der in der Vorlesung erlernten Konzepte und Techniken eigene Lösungen in diesem Modell entwerfen, analysieren und die Eigenschaften beweisen.

Inhalt der Lehrveranstaltung

Räumliche Daten werden in den unterschiedlichsten Bereichen der Informatik verarbeitet, z.B. in Computergrafik und Visualisierung, in geographischen Informationssystemen, in der Robotik usw. Die algorithmische Geometrie beschäftigt sich mit dem Entwurf und der Analyse geometrischer Algorithmen und Datenstrukturen. In diesem Modul werden häufig verwendete Techniken und Konzepte der algorithmischen Geometrie vorgestellt und anhand ausgewählter und anwendungsbezogener Fragestellungen vertieft. Konkrete Vorlesungsthemen sind Algorithmen und Datenstrukturen für:

  • konvexe Hülle
  • Linienschnitte
  • Polygontriangulierung
  • Bereichsabfragen
  • Punktlokalisierung
  • Voronoi-Diagramme und Delaunay-Triangulierungen
  • Dualität von Punkten und Geraden
  • Quadtrees
  • Well-Separated Pair Decomposition

Weitere Informationen

ECTS-Breakdown

25 h Vorlesung und Übung
30 h Nachbereitung der Vorlesung und Vorbereitung der Übungen
19 h Prüfungsvorbereitung
  1 h Mündliche Prüfung
------
75 h gesamt 

Allgemeine und organisatorische Fragen bitte an alggeom@ac.tuwien.ac.at.

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Di.09:00 - 11:0002.10.2018 - 15.01.2019Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.14:00 - 16:0003.10.2018 - 30.01.2019Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Mi.12:00 - 14:0014.11.2018Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.15:00 - 17:0021.11.2018Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Mi.15:00 - 17:0005.12.2018Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Algorithmic Geometry - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.02.10.201809:00 - 11:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.03.10.201814:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Di.09.10.201809:00 - 11:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.10.10.201814:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Di.16.10.201809:00 - 11:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.17.10.201814:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Di.23.10.201809:00 - 11:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.24.10.201814:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Di.30.10.201809:00 - 11:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.31.10.201814:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Di.06.11.201809:00 - 11:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.07.11.201814:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Di.13.11.201809:00 - 11:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.14.11.201812:00 - 14:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.14.11.201814:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Di.20.11.201809:00 - 11:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.21.11.201815:00 - 17:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung
Di.27.11.201809:00 - 11:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Di.04.12.201809:00 - 11:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.05.12.201815:00 - 17:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung/Übung

Leistungsnachweis

Die Gesamtnote setzt sich zusammen aus einer mündlichen Prüfung (70%) und der Leistung in  den Übungen (30%).

Prüfungen

TagZeitDatumOrtPrüfungsmodusAnmeldefristAnmeldungPrüfung
Mo.09:00 - 10:4013.01.2020 beurteilt13.12.2019 00:01 - 10.01.2020 23:59in TISSAlgorithmic Geometry Oral Exam
Mo.10:45 - 12:0013.01.2020 beurteilt13.12.2019 00:01 - 10.01.2020 23:59in TISSAlgorithmic Geometry Oral Exam
Mi.09:20 - 10:5504.03.2020 HC 04 11beurteilt06.12.2019 00:01 - 02.03.2020 23:59in TISSAlgorithmic Geometry Oral Exam
Mi.11:00 - 12:3504.03.2020 HC 04 11beurteilt06.12.2019 00:01 - 02.03.2020 23:59in TISSAlgorithmic Geometry Oral Exam

LVA-Anmeldung

Von Bis Abmeldung bis
22.09.2018 00:00 12.10.2018 00:00 23.10.2018 00:00

Gruppen-Anmeldung

GruppeAnmeldung VonBis
Group 102.10.2018 08:0008.10.2018 23:59

Curricula

Literatur

Vortragsfolien bzw. Artikel zu bestimmten Themen werden in der Vorlesung kostenlos verteilt und/oder zum Download angeboten.

Empfohlene Literatur:

M. de Berg, O. Cheong, M. van Kreveld, M. Overmars:
Computational Geometry Algorithms and Applications, Springer 2008.

D. Mount:
CMSC 754 Computational Geometry Lecture Notes, U. Maryland 2014.

Vorkenntnisse

Grundkenntnisse in Entwurf und Analyse von Algorithmen

Vorlesungsfolien werden zur Verfügung gestellt

Sprache

Englisch