Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
|
 |
|
|
|
|
|
| Date | Content | Exercises | Lecture notes | ||
| #1 (18.9.2008) | Information about the course, applications of geometry | Exercise 1 | Introductory slides | ||
| #2 (22.9.2008) | Convexity, convex hull, algorithms (Jarvis wrap, SLR) | Exercise 2 | Chapter 1 | ||
| #3 (25.9.2008) | Faster convex hull (Chan's algorithm) | Homework 1 | Chapter 2 | ||
| #4 (29.9.2008) | Line Segment Intersection | Exercise 3 | Chapter 3-4 | ||
| #5 (2.10.2008) | Red-blue intersections | - | - | ||
| #6 (6.10.2008) | Planar graphs | Exercise 4 | Chapter 5 | ||
| #7 (9.10.2008) | Counting triangulations: historical overview (by E. Welzl) | - | - | ||
| #8 (13.10.2008) | Delaunay triangulations | Exercise 5 | Chapter 6 | ||
| #9 (15.10.2008) | Convex hull in higher dimensions | Homework 2 | - | ||
| #10 (20.10.2008) | Voronoi diagrams | Exercise 6 | Chapter 8 | ||
| #11 (23.10.2008) | Kirkpatrick's hierarchy | - | Chapter 9 | ||
| #12 (27.10.2008) | Randomized incremental construction | Exercise 7 | Slides | ||
| #13 (30.10.2008) | Trapezoid decomposition | - | Slides | ||
| #14 (3.11.2008) | Line arrangements | Exercise 8 | Chapter 10 | ||
| #15 (6.11.2008) | Visibility Graphs | Homework 3 | Chapter 11 | ||
| #16 (10.11.2008) | 3-Sum | Exercise 9 | Chapter 12 | ||
| #17 (13.11.2008) | Davenport-Schinzel Sequences | - | Chapter 13 | ||
| #18 (17.11.2008) | Single Faces in Arrangements | Exercise 10 | Chapter 14 | ||
| #19 (19.11.2008) | Single Faces in Arrangements | - | - | ||
| #20 (24.11.2008) | Range trees | Homework 4 | Chapter 15 | ||
| #21 (27.11.2008) | Smallest enclosing balls | - | Chapter 16 | ||
| #22 (1.12.2008) | Smallest enclosing balls | Exercise 11 | - | ||
| #23 (4.12.2008) | Smallest enclosing balls | - | - | ||
| #24 (8.12.2008) | Rayshooting | - | Chapter 18 | ||
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.
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.
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.
Outlook: In the spring semester 2009 the following geometry related courses are planned:
- Approximation Algorithms and Semidefinite Programming (B. Gärtner, J. Matoušek)
- 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.
- Bernds Skript for a course held in Berlin in 1996
.
.
.