Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Computational Geometry HS09 - course at ETH Zurich
Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

Computational Geometry (251-1425-00L) HS09


Time & Place

Lecture: Monday 13:15-15:00 CAB G59 and Thursday 13:15-14:00 CAB G51. The lecturers are:
Bernd Gärtner, CAB G32.2, Tel: 044 632 70 26, .
Michael Hoffmann, CAB G33.1, Tel: 044 632 73 90, .
Exercise: Thursday 14:15-16:00, CAB G51. The teaching assistant is:
Tobias Christ, CAB G36.1, Tel: +41-44-632 75 49, .



Course Material

Information about the course, applications of geometryConvex Hull

Date Content Exercises Lecture notes and links

#1 (17.9.2009) Exercise 1

#2 (21.9.2009) Exercise 2 Lecture 1

#3 (24.9.2009) Faster convex hull (Chan's algorithm) Lecture 2

#3 (28.9.2009) Triangulations Exercise 3 Lecture 3

#4 (1.10.2009) Triangulations of Convex Polygons - A Historical Note (by Emo Welzl) Homework 1

#5 (5.10.2009) Delaunay Triangulations Exercise 4 Lecture 4

#6 (8.10.2009) Incremental Construction of the Delaunay Triangulation Lecture 5

#7 (12.10.2009) Randomized Incremental Construction (RIC); Voronoi Diagrams Exercise 5 Slides (RIC), Lecture 6

#8 (15.10.2009) Kirkpatrick's hierarchy Homework 2 Lecture 7

#9 (19.10.2009) Randomized Incremental Construction (RIC), Part II; Trapezoidal map Exercise 6 Lecture 8, Slides (trapezoidal map)

#10 (22.10.2009) Triangulating a Simple Polygon with Fast Trapezoidal Maps Slides (trapezoidal map)

#11 (26.10.2009) Line Segment Intersections Exercise 7 Lecture 9

#12 (29.10.2009) Randomized incremental construction of line segment intersections

#13 (2.11.2009) Line Arrangements Exercise 8 Lecture 10

#14 (5.11.2009) Computing Ham-Sandwich Cuts in 2D Homework 3 Lecture 11

#15 (9.11.2009) Visibility Graphs and 3-Sum Lecture 12

#16 (12.11.2009) Linear Programming Exercise 9 Lecture 13

#17 (16.11.2009) Linear Programming: A Randomized Algorithm Exercise 10 Lecture 14

#18 (19.11.2009) Linear Programming: A Randomized Algorithm II Lecture 15

#19 (23.11.2009) Smallest Enclosing Balls - Basics Exercise 11 Lecture 16

#20 (26.11.2009) Smallest Enclosing Balls - Swiss Algorithm Homework 4 Lecture 17

#21 (30.11.2009) Davenport-Schinzel Sequences Exercise 12 Lecture 18

#22 (3.12.2009) Translational Motion Planning Lecture 19

#23 (7.12.2009) Pseudotriangulations Exercise 13 Lecture 20

#24 (10.12.2009)

#25 (14.12.2009) Range Trees Lecture 22

#26 (17.12.2009)


Course Description

Computational Geometry is about design and analysis of efficient algorithms for geometric problems, typically in low dimensions (2,3,..). These are needed in 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. Its 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.

Covered topics include convex hulls, Delaunay triangulations, Voronoi diagrams, arrangements, point location, range, segment and interval trees, smallest enclosing balls, hard geometric problems, and curve reconstruction.


Procedures, exercises, exam

Every week we provide you with an exercise sheet. You should solve it in written form and return your solutions the week after. Your solutions are thoroughly commented and graded, but they do not count towards your final grade. The motivation to work on the exercises stems from your interest in the topic (and possibly also the desire to succeed in the exam :-)).

In Addition, you receive four small projects during the semester. Also these projects are to be solved in written form, but typically you have two weeks of time to return your solutions/reports, typeset in LaTeX. In contrast to the exercises, projects do count towards the final grade: Your three best grades will account for 10% of your final grade each. Solving projects in teams is not allowed.

There is an oral exam of 30 minutes during the examination period. Your final grade consists to 70% of the grade for the exam and to 30% of the grade for the projects.

You are expected to learn proofs discussed in the lecture, should be able to explain their basic ideas and reproduce more details on demand. You should also be able to give a short presentation on any topic treated throughout the course.

One of the questions given to you during the exam is to solve one of the exercises posed throughout the semester.

Roughly half an hour before the exam you get to know the exercise to be solved and one topic that you will be questioned about in particular, that is, you have 30 minutes preparation time. For this preparation, paper and pencil will be provided. You may not use any other material, like books or notes.

For PhD students the following rule applies for obtaining credit points (KE) for the course. If you successfully solve (grade 4.0 or better) three out of the four special exercises you get a "Testat" and 5KE. In order to obtain the remaining 3 KE, you have to take and pass the final exam. No credit points are given for simply sitting in the course.


Complementary Courses & Semester/Master/Diploma Theses

This course is complemented by a seminar that takes place every spring semester. Furthermore, after  having completed the course and the seminar, it is possible to do a semester, master or diploma thesis in the area of Computational Geometry. Students are also welcome at our graduate seminar.


Literature and Links