Preface
These lecture notes are designed to accompany a course on “Computational Geometry”
that we teach at the Department of Computer Science, ETH Zürich, in every winter term
since 2005. The course has evolved over the years and so have the notes, a first version of
which was published in 2008. In the current setting, the course runs over 14 weeks, with
three hours of lecture and two hours of exercises each week. In addition, there are three
sets of graded homeworks which students have to hand in spread over the course. The
target audience are third-year Bachelor or Master students of Mathematics or Computer
Science.
The selection of topics and their treatment is somewhat subjective, beyond what
we consider essentials driven by the (diverse) research interests within our working
group. There is a certain slant towards algorithms rather than data structures and a
fair amount of influx from combinatorial geometry. The focus is on low-dimensional
Euclidean space (mostly 2D), although we sometimes discuss possible extensions and/or
remarkable differences when going to higher dimensions. At the end of each chapter
there is a list of questions that we expect our students to be able to answer in the oral
exam.
Most parts of these notes have gone through a number of proof-readings, but expe-
rience tells that there are always a few mistakes that escape detection. So in case you
notice some problem, please let us know, regardless of whether it is a minor typo or
punctuation error, a glitch in formulation, or a hole in an argument. This way the issue
can be fixed for the next edition and future readers profit from your findings.
We thank Tobias Christ, Anna Gundert, Gabriel Nivasch, Júlia Pap, Marek Sulovský,
May Szedlák, and Hemant Tyagi for pointing out errors in preceding versions.
Bernd Gärtner and Michael Hoffmann
Institute of Theoretical Computer Science
ETH Zürich
Universitätstrasse 6
CH-8092 Zürich
Switzerland
E-mail address: {gaertner,hoffmann}@inf.ethz.ch
3
