Students acquire a systematic understanding of algorithmic problems and solution approaches in the area of computational geometry, which builds upon their existing knowledge of theoretical computer science and algorithmics. After successful participation in this course students shall be able to

• explain concepts, structures and problem definitions that were presented in class
• execute algorithms on example instances, analyze them precisely and prove their properties
• select which algorithms and data structures are suitable for solving a given geometric problem and adapt them appropriately
• analyze new geometric problems, reduce them to their algorithmic core, and design appropriate abstract models; based on the concepts and techniques presented in class, they can subsequently design and analyze their own algorithms in these models.

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

ECTS-Breakdown

25 h lectures
20 h lecture follow-up and preparation of home exercises
  5 h presentation of home exercises
24 h preparation for oral exam
  1 h oral exam
------
75 h overall

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

The lecture is held by: Martin Nöllenburg

Active participation in the home exercises is required. The final examination will be an oral exam.

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.

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

Lecture slides will be made available to the students.