# 192.133 Algorithmic Geometry This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",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_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2023W 2022W

2023W, VU, 3.0h, 4.5EC

## Properties

• Semester hours: 3.0
• Credits: 4.5
• Type: VU Lecture and Exercise
• Format: Presence

## 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 exercise groups
• Lectures and exercises will take place physically and may be supplemented by video recordings

## Mode of examination

Immanent

### ECTS-Breakdown

40 h attending lectures and exercises
50 h lecture follow-up and preparation of home exercises
22 h preparation for oral exam
0.5 h oral exam
------
112.5 h overall

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

## Course dates

DayTimeDateLocationDescription
Tue09:00 - 11:0003.10.2023 - 23.01.2024Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Wed15:00 - 17:0004.10.2023 - 24.01.2024Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Wed16:00 - 18:0024.01.2024Seminarraum FAV 01 A (Seminarraum 183/2) Übung
Algorithmic Geometry - Single appointments
DayDateTimeLocationDescription
Tue03.10.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Wed04.10.202315:00 - 17:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Tue10.10.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Wed11.10.202315:00 - 17:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Tue17.10.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Wed18.10.202315:00 - 17:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Tue24.10.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Wed25.10.202315:00 - 17:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Tue31.10.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Tue07.11.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Wed08.11.202315:00 - 17:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Tue14.11.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Tue21.11.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Wed22.11.202315:00 - 17:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Tue28.11.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Wed29.11.202315:00 - 17:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Tue05.12.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Wed06.12.202315:00 - 17:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Tue12.12.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Wed13.12.202315:00 - 17:00Seminarraum FAV 05 (Seminarraum 186) Lecture/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%.

## Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Tue09:00 - 12:0013.02.2024Seminarraum FAV 01 A (Seminarraum 183/2) assessed11.01.2024 00:00 - 12.02.2024 12:59TISSAlgorithmic Geometry Exam
Tue09:00 - 13:0027.02.2024Seminarraum FAV 01 A (Seminarraum 183/2) assessed21.02.2024 00:00 - 25.02.2024 23:59TISSAlgorithmic Geometry Exam

## Course registration

Begin End Deregistration end
31.08.2023 00:00 10.10.2023 23:59 17.10.2023 23:59

## Group Registration

GroupRegistration FromTo
Exercise group03.10.2023 09:0011.10.2023 23:59

## Curricula

Study CodeObligationSemesterPrecon.Info
066 645 Data Science Not specified
066 926 Business Informatics Not specified
066 931 Logic and Computation Mandatory elective
066 932 Visual Computing Mandatory elective
066 937 Software Engineering & Internet Computing Mandatory elective
066 938 Computer Engineering Not specified

## Literature

No lecture notes are available.

## Previous knowledge

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

English