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

252-1425-00L 8 Credits BSC , DR , MSC , WBZ D-MATH , D-INFK
You're viewing possible stale or outdated data. Please check the latest semester for more up-to-date information.

Geometry: Combinatorics and Algorithms

Lecturers & Examiners: Prof. em. Dr. Emo Welzl, Prof. Dr. Bernd Gärtner, Dr. Michael Hoffmann, Dr. Manuel Wettstein
VVZ CR 4.2

Last Updated: 2026-02-05 15:35:54

Abstract

Geometric structures are useful in many areas, and there is a need to understand their structural properties, and to work with them algorithmically. The lecture addresses theoretical foundations concerning geometric structures. Central objects of interest are triangulations. We study combinatorial (Does a certain object exist?) and algorithmic questions (Can we find a certain object efficiently?)

Objective

The goal is to make students familiar with fundamental concepts, techniques and results in combinatorial and computational geometry, so as to enable them to model, analyze, and solve theoretical and practical problems in the area and in various application domains. In particular, we want to prepare students for conducting independent research, for instance, within the scope of a thesis project.

Content

Planar and geometric graphs, embeddings and their representation (Whitney's Theorem, canonical orderings, DCEL), polygon triangulations and the art gallery theorem, convexity in R^d, planar convex hull algorithms (Jarvis Wrap, Graham Scan, Chan's Algorithm), point set triangulations, Delaunay triangulations (Lawson flips, lifting map, randomized incremental construction), Voronoi diagrams, the Crossing Lemma and incidence bounds, line arrangements (duality, Zone Theorem, ham-sandwich cuts), 3-SUM hardness, counting planar triangulations.

Resources

Lecture Notes

yes

Literature

Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong, Computational Geometry: Algorithms and Applications, Springer, 3rd ed., 2008. Satyan Devadoss, Joseph O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011. Stefan Felsner, Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry, Teubner, 2004. Jiri Matousek, Lectures on Discrete Geometry, Springer, 2002. Takao Nishizeki, Md. Saidur Rahman, Planar Graph Drawing, World Scientific, 2004.

Learning Materials (Links)

General Information

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

Examination

Type
session examination
Mode
oral 30 minutes
70% final oral exam: 30 minutes oral exam with 30 minutes preparation time (no material allowed).30% project work (compulsory continuous performance assessment): At times during the semester, we hand out specially marked projects. The written part of the solutions are expected typeset in LaTeX or similar. Solutions are graded, and the best three grades will account for 10% of the final grade each. Projects can be discussed with colleagues, but we expect an independent writeup.

Course Components

Type Title Time & Place Hours
lecture Geometry: Combinatorics and Algorithms
  • Mon 13:15-14:00 (CAB G 11)
  • Thu 14:15-16:00 (HG G 3)
3 h weekly
exercise Geometry: Combinatorics and Algorithms
  • Thu 16:15-18:00 (CAB G 51)
2 h weekly
independent project Geometry: Combinatorics and Algorithms
Project Work, no fixed presence required.
No time listed 2 h weekly

Offered In