VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

251-1425-00L 8 Credits BSC , DS , MSC , WBZ D-MATH , D-INFK , D-BAUG

Computational Geometry

Lecturers & Examiners: Prof. Dr. Bernd Gärtner, Dr. Michael Hoffmann
VVZ CR n/a

Last Updated: 2026-02-05 15:24:46

Abstract

Computational Geometry is about design and analysis of efficient algorithms for geometric problems, typically in low dimensions (2,3,..). These are needed for many application domains, such as geographic information systems, computer graphics, or geometric modeling. The lecture addresses basic geometric data structures and introduces important design paradigms for geometric algorithms.

Objective

The goal is to make students familiar with the important techniques and results in computational geometry, and to enable them to attack theoretical and practical problems in various application domains.

Content

Convex hulls, Delaunay triangulations, Voronoi diagrams, arrangements, point location, range and segment trees, smallest enclosing balls, hard geometric problems, curve reconstruction,...

Resources

Literature

Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer, 2000. Franco P. Preparata, Michael I. Shamos, Computational Geometry: An Introduction, Springer, 1985.

General Information

Language
English
Levels
BSC , DS , MSC , WBZ
Frequency
Yearly recurring

Examination

Type
session examination
Mode
oral 30 minutes
70% of the final grade are determined by a 30 minute oral exam with 30 minute preparation time. 30% are determined by the achieved points on specially marked exercise sets throughout the semester.

Course Components

Type Title Time & Place Hours
lecture Computational Geometry
  • Mon 14:15-16:00 (CAB G 59)
  • Thu 13:15-14:00 (CAB G 59)
3 h weekly
exercise Computational Geometry
  • Thu 14:15-16:00 (IFW A 32.1)
2 h weekly

Offered In