# 186.122 Algorithmic Geometry This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_20",{id:"j_id_20",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_22",{id:"j_id_22",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2021W 2020W 2019W 2018W 2017W 2016W 2015W 2014W 2013W 2012W 2010W 2009W 2008W 2007W 2006W 2005W 2004W 2003W 2002W

2020W, VU, 2.0h, 3.0EC

## Properties

• Semester hours: 2.0
• Credits: 3.0
• Type: VU Lecture and Exercise
• 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
• 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

### Distance Learning

This course takes place in "distance learning" mode. We provide learning videos once per week, which can be watched asynchronously. The exercise part consists of multiple exercise sheets to be solved and handed in. Further we will offer electronic live meetings every few weeks to discuss and deepen the course material (Tuesdays from 9:00-11:00). Finally, we use quizzes and discussion forums in TUWEL.

The firs lecture takes place live on October 6, 2020 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.

## Course dates

DayTimeDateLocationDescription
Tue09:00 - 11:0006.10.2020 Zoom Meeting (LIVE)Introductory Lecture
Tue09:00 - 11:0020.10.2020 - 01.12.2020 Zoom Meeting (LIVE)Live Webinar
Tue09:00 - 11:0027.10.2020 - 24.11.2020 Zoom Meeting (LIVE)Exercise Session
Tue09:00 - 11:0015.12.2020 Zoom Meeting (LIVE)Exercise Session
Algorithmic Geometry - Single appointments
DayDateTimeLocationDescription
Tue06.10.202009:00 - 11:00 Zoom MeetingIntroductory Lecture
Tue20.10.202009:00 - 11:00 Zoom MeetingLive Webinar
Tue27.10.202009:00 - 11:00 Zoom MeetingExercise Session
Tue03.11.202009:00 - 11:00 Zoom MeetingLive Webinar
Tue10.11.202009:00 - 11:00 Zoom MeetingExercise Session
Tue17.11.202009:00 - 11:00 Zoom MeetingLive Webinar
Tue24.11.202009:00 - 11:00 Zoom MeetingExercise Session
Tue01.12.202009:00 - 11:00 Zoom MeetingLive Webinar
Tue15.12.202009:00 - 11:00 Zoom MeetingExercise Session

## 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%.

## Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Wed - 12.01.2022assessed03.12.2021 18:00 - 07.01.2022 23:59TISSAlgorithmic Geometry Oral Exam
Wed - 02.02.2022assessed03.12.2021 18:00 - 28.01.2022 23:59TISSAlgorithmic Geometry Oral Exam
Wed - 23.02.2022assessed03.12.2021 18:00 - 18.02.2022 23:59TISSAlgorithmic Geometry Oral Exam

## Course registration

Begin End Deregistration end
03.09.2020 00:00 09.10.2020 00:00 20.10.2020 00:00

## Group Registration

GroupRegistration FromTo
Group 106.10.2020 08:0014.10.2020 23:59

## Literature

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.

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

English