186.122 Algorithmic Geometry
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2021W, VU, 2.0h, 3.0EC
Lecture TubeTUWEL

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise
  • LectureTube course
  • Format: Distance Learning

Learning outcomes

After successful completion of the course, students are able to

  • explain fundamental concepts, structures and problem definitions in algorithmic geometry
  • explain, assess, and analyze the discussed algorithms
  • select and adapt appropriate algorithms and data structures to related problems
  • model and analyze unknown applied or theoretical geometric problems and develop and possibly implement efficient solutions independently

Subject of course

Spatial data are processed in various subfields of computer science, e.g. in computer graphics, visualization, geographic information systems, robotics etc. The area of computational geometry deals with the design and analysis of geometric algorithms and data structures. In this module we present common techniques and concepts in computational geometry in the context of selected and applied geometric questions. The following topics are covered in the course:

  • convex hulls
  • line segment intersections
  • polygon triangulation
  • range queries
  • point location
  • Voronoi diagrams and Delaunay triangulations
  • duality of points and lines
  • quadtrees
  • well-separated pair decomposition
  • visibility graphs

Teaching methods

  • Definition, design and analysis of algorithms and data structures, discussion and formal proofs of algorithmic and geometric properties, examples
  • Joint and independent solving of exercise and example tasks
  • Discussion of exercise tasks and proof ideas in (virtual) exercise groups
  • Lecture content will be provided weekly as recorded videos; live discussions will help consolidating the material.

Mode of examination

Immanent

Additional information

Distance Learning

This course takes place in hybrid "distance learning" mode. There will be four blocks of lectures, for which learning videos and material are provided that can be watched asynchronously. The exercise part consists of one exercise sheet per block to be solved and handed in. The discussion of the exercises takes place in a hybrid live exercise session (physically in a seminar room and streamed via Zoom). Further we will offer an electronic live meeting for each block to discuss and deepen the course material (Wednesdays from 14:00-16:00). Finally, we use quizzes and discussion forums in TUWEL.

The first lecture takes place live on October 5, 2021 from 9:00-11:00 in Zoom. The Zoom URL will be announced to all registered students before the first lecture.

 

ECTS-Breakdown

25 h attending lectures and exercises
30 h lecture follow-up and preparation of home exercises
19.5 h preparation for oral exam
0.5 h oral exam
------
75 h overall

Please send mails concerning general and organisational issues to alggeom@ac.tuwien.ac.at.

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Tue09:00 - 11:0005.10.2021 Zoom (LIVE)Introduction
Wed14:00 - 16:0013.10.2021 - 01.12.2021 Zoom (LIVE)Q&A session
Wed14:00 - 16:0020.10.2021 - 24.11.2021Seminarraum FAV EG C (Seminarraum Gödel) (LIVE)Exercise
Tue14:00 - 16:0007.12.2021Seminarraum FAV EG C (Seminarraum Gödel) (LIVE)Exercise
Algorithmic Geometry - Single appointments
DayDateTimeLocationDescription
Tue05.10.202109:00 - 11:00 ZoomIntroduction
Wed13.10.202114:00 - 16:00 ZoomQ&A session
Wed20.10.202114:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Exercise
Wed03.11.202114:00 - 16:00 ZoomQ&A session
Wed10.11.202114:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Exercise
Wed17.11.202114:00 - 16:00 ZoomQ&A session
Wed24.11.202114:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Exercise
Wed01.12.202114:00 - 16:00 ZoomQ&A session
Tue07.12.202114:00 - 16:00Seminarraum FAV EG C (Seminarraum Gödel) Exercise

Examination modalities

  • Solve and hand-in exercise sheets with theoretical questions
  • Implementation of algorithms (optional)
  • Present and discuss the course content in an oral exam

The oral exam counts for 70% of the grade, the exercise coursework for 30%.

Course registration

Begin End Deregistration end
02.09.2021 00:00 08.10.2021 00:00 19.10.2021 00:00

Group Registration

GroupRegistration FromTo
Group 105.10.2021 08:0013.10.2021 23:59

Curricula

Literature

Lecture notes and papers covering selected topics are handed out for free during lectures, and/or are made available for download.

Recommended literature:

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.

 

M. Smid: http://people.scs.carleton.ca/~michiel/aa-handbook.pdf

Previous knowledge

A solid knowledge of the design and analysis of algorithms is recommended.

Lecture slides and videos will be made available to the students.

Language

English