| Carl-Friedrich-Gauß-Fakultät | Informatik

Computational Geometry

SemesterWintersemester 2015/2016 [ Andere Semester: · Winter 14/15 · Winter 13/14 · Winter 12/13 ]
Modulnr. INF-ALG-18 , INF-ALG-18
Veranst.Nr.INF-ALG-007, INF-ALG-008
Studieng.Diplom Informatik, Master Informatik, Diplom Wirtschaftsinformatik, Master Wirtschaftsinformatik
IBR Gruppe(n)ALG (Prof. Fekete)
PhotoProf. Dr. Sándor P. Fekete
+49 531 3913111
Raum 335
PhotoDr. Victor Alvarez
Ehemaliger Wissenschaftlicher Mitarbeiter
AssistentMelanie Papenberg
Ort & Zeit Lecture: Tuesday, 09:45 - 11:15 hrs., IZ 305

Tutorial: Thursday, 15:00 - 16:30 hrs., IZ 305, bi-weekly
Small Tutorial: Thursday, 15:00 - 16:30 hrs., IZ 305, bi-weekly. Tutor: Melanie Papenberg

Beginn First Lecture: Tuesday, 03.11.2015
First Tutorial: Thursday, 19.11.2015
First Small Tutorial: Thursday, 26.11.2015
VoraussetzungenBasic knowledge of analysis of Algorithms and Data Structures is required. Basic knowledge of probability is useful but not required.
ScheinerwerbHomework assignments during the semester (=Studienleistung) and one exam at the end.

This course is meant to be a first course in Computational Geometry. After this course, the participants will have acquired good knowledge about core topics in Computational Geometry that by now have gathered a significant amount of research and practical applications. The participants will be able to handle common design paradigms of geometric algorithms such as divide-and-conquer, sweep-line, as well as probabilistic. They will also be able to design and analyze geometric algorithms taking into consideration inherent intricacies of geometric computations. Topics on this course include among other:

  1. Geometric Primitives
  2. Convex Hulls
  3. Polygon Triangulation
  4. Voronoi Diagrams
  5. Delaunay Triangulation
  6. Point Location and Proximity
  7. Degeneracies and Robustness
  8. Arrangements and Duality

Literatur/Links The course will not follow any book in particular but below there is a list of relevant literature.

General Information

  • Schedule of all lectures, tutorials, and home assignments: PDF [20.10.2015]
  • There is a mailinglist. We will distribute the homework sets and other announcements via this list, so, please subscribe!

Homework Sets

  1. Set 1: [PDF] Out: 09.11.2015. Due: 23.11.2015.
  2. Set 2: [PDF] Out: 23.11.2015. Due: 07.12.2015.
  3. Set 3: [PDF] Out: 07.12.2015. Due: 04.01.2016.
  4. Set 4: [PDF] Out: 04.01.2016. Due: 18.01.2016.
  5. Set 5: [PDF] Out: 22.01.2016. Due: 05.02.2016.

aktualisiert am 22.01.2016, 14:08 von Dr. Victor Alvarez