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, homeworks and links | ||
| #1 Tuesday 17.09.2013 | Information about the course, applications of geometry | Introductory Slides | |||
| #2 Thursday 19.09.2013 | Fundamentals, Polygons, Triangulations | 2.2, 2.6, 2.13 | Lecture Notes - Chapters 1 and 2 | ||
| #3 Tuesday 24.09.2013 | Art Gallery Problem, Convex Sets | ||||
| #4 Thursday 26.09.2013 | Convex Sets, Convex Hull | 2.16, 3.16 | Homework 1 | ||
| #5 Tuesday 01.10.2013 | Convex Hull | Lecture Notes - Chapter 3 | |||
| #6 Thursday 03.10.2013 | Convex Hull, Plane Graphs, DCEL | 3.11, 3.20, 3.22, 3.24 | Lecture Notes - Chapter 4 | ||
| #7 Tuesday 08.10.2013 | Line Sweep | Slides | |||
| #8 Thursday 10.10.2013 | Algebraic Degree, Red-Blue Intersections | 5.14, 5.17, 5.19 | Lecture Notes - Chapter 5 | ||
| #9 Tuesday 15.10.2013 | Triangulation of a Point Set | Lecture Notes - Chapter 5 - UPDATE | |||
| #10 Thursday 17.10.2013 | Delaunay Triangulation, Lawson Flip | 6.3, 6.6, 6.7 | Lecture Notes - Chapter 6 | ||
| #11 Tuesday 22.10.2013 | Lawson Flip Algorithm | Homework 2 On Exercise 3: The talks will take place on the 14th of November, during the exercise session. |
|||
| #12 Thursday 24.10.2013 | Delaunay Graph, Smallest Angle | 6.14, 6.22 | |||
| #13 Tuesday 29.10.2013 | Randomized Incremental Construction | Lecture Notes - Chapter 7 | |||
| #14 Thursday 31.10.2013 | Randomized Incremental Construction (cont.), Configuration Space Framework | No Exercise Session | Lecture Notes - Chapter 8 | ||
| #15 Tuesday 05.11.2013 | Configuration Space Framework (cont.) | ||||
| #16 Thursday 07.11.2013 | Configuration Space Framework (cont.), Application to Convex Hull | 7.4, 8.7 | |||
| #17 Tuesday 12.11.2013 | Voronoi Diagrams | Lecture Notes - Chapter 9 | |||
| #18 Thursday 14.11.2013 | Voronoi Diagrams (cont.), Kirkpatrick's Hierarchy | Student Talks | |||
| #19 Tuesday 19.11.2013 | Trapezoidal Map | Lecture Notes - Chapter 10 | |||
| #20 Thursday 21.11.2013 | Trapezoidal Map (cont.) | 9.21, 9.23, 10.23 | |||
| #21 Tuesday 26.11.2013 | Line Arrangements | Lecture Notes - Chapter 11 | |||
| #22 Thursday 28.11.2013 | Zone Theorem, Minimum Area Triangle, Visibility Graphs | 11.2, 11.3, 11.6 | Homework 3 | ||
| #23 Tuesday 03.12.2013 | Visibility Graphs (cont.), Ham-Sandwich Cuts | ||||
| #24 Thursday 05.12.2013 | Ham-Sandwich Cuts(cont.), 3-Sum, Davenport-Schinzel Sequences | 11.18, 11.20, 12.6, 12.7 | Lecture Notes - Chapter 12 | ||
| #25 Tuesday 10.12.2013 | Davenport-Schinzel Sequences (cont.) | ||||
| #26 Thursday 12.12.2013 | Epsilon nets | 12.9, 12.11, 13.4, 13.5 | Lecture Notes - Chapter 13 | ||
| #27 Tuesday 17.12.2013 | Epsilon nets | ||||
| #28 Thursday 19.12.2013 | Epsilon nets | Lecture Notes - Chapter 13 - UPDATE | |||
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 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, line sweep algorithms, Delaunay triangulation, randomized incremental constructions, trapezoidal decomposition, Voronoi diagrams, pesudotriangulation, linear programming, smallest enclosing balls, arrangements, Davenport-Schinzel sequences, motion planning, and epsilon nets.
Every week we provide you with exercises. You should solve them in written form and you are encouraged to hand in your solutions to the teaching assistant. Your solutions are thoroughly commented, 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 three homework assignments during the semester. The homework is to be solved in written form and typically you have two weeks of time to return your solutions/reports, typeset in LaTeX. In contrast to the exercises, these assignments do count towards the final grade: Your three grades will account for 10% of your final grade each. Solving the homework in teams is not allowed. Besides one or two exercises, the homework may include a small research project, or you are asked to give a short talk about your last small research project.
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 homework assignments.
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 same rules apply for obtaining credit points as for all other participants. Taking the exam and achieving an overall grade of at least 4.0 (computed as a weighted average of grades for homework and the written final exam as detailed above) qualifies for receiving credits. In order to comply with new regulations recently issued by the department, merely attending the course and/or handing in exercises is no longer sufficient.
This course is complemented by the seminar Computational Geometry and Graph Drawing which also runs this semester. After having completed both 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.
- Satyan L. Devadoss and Joseph O'Rourke Discrete and Computational Geometry, Princeton University Press, 2011.
- Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry: Algorithms and Applications, Springer, 3rd edition, 2008.
- Franco P. Preparata, Michael I. Shamos, Computational Geometry: An Introduction, Springer, 1985.
- Bernds Skript for a course held in Berlin in 1996
- New to LaTex? Look at Tobias Oetiker's Not So Short Introduction to LaTeX.
- No idea how to run LaTex on your Window Computer? The usual (La)TeX distribution for Windows is MiKTeX
.