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

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

• 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

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.

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

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