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
| Bernd Gärtner, | OAT Z15, | gaertner@inf.ethz.ch |
| Michael Hoffmann, | OAT Z13.1, | hoffmann@inf.ethz.ch |
| Patrick Schnider, | OAT Z13.1, | patrick.schnider@inf.ethz.ch |
| Emo Welzl, | OAT Z13.2, | emo@inf.ethz.ch |
| Patryk Morawski, | pmorawski@student.ethz.ch | |
| Meghana M Reddy [contact assistant], | OAT Z18, | meghana.mreddy@inf.ethz.ch |
| Date | Content | Exercises and links | Lecture notes | Lecturer |
| #1 21.09.2023 | Information about the course, geometric graphs | Chapter 1, Chapter 2.1-2.2, Slides | MH | |
| #2 25.09.2023 | Graph planarity | Exercise 1 | Chapter 2.3-2.4, Slides | BG |
| #3 28.09.2023 | Unique embeddings | Slides | BG | |
| #4 02.10.2023 | Unique embeddings | Exercise 2 | Slides | MH |
| #5 05.10.2023 | Canonical Orderings, The Shift Algorithm | Chapter 2.5, Slides | MH | |
| #6 09.10.2023 | The Shift Algorithm | Exercise 3 | Slides | MH |
| #7 12.10.2023 | Crossings | Homework 1 | Chapter 3, Slides | MH |
| #8 16.10.2023 | Crossings, Polygons | Exercise 4 | Chapter 4, Slides | MH |
| #9 19.10.2023 | Polygons, Convexity | Chapter 5, Slides | PS | |
| #10 23.10.2023 | Convexity | Exercise 5 | Slides | PS |
| #11 26.10.2023 | Convexity algorithms | Slides | PS | |
| #12 30.10.2023 | Delaunay Triangulations | Exercise 6 | Chapter 6, Slides | PS |
| #13 02.11.2023 | Delaunay triangulation | Slides | PS | |
| #14 06.11.2023 | Incremental Construction | Exercise 7 | Chapter 7, | PS |
| #15 13.11.2023 | Voronoi Diagrams | Exercise 8 | Chapter 8, Slides | PS |
| #16 16.11.2023 | Voronoi Diagrams, Polytopes | Homework 2 | Chapter 9, Slides | BG |
| #17 20.11.2023 | Polytopes | Exercise 9 | BG | |
| #18 23.11.2023 | Polytopes | BG | ||
| #19 27.11.2023 | Polytopes, Line Arrangements | Chapter 10, Slides | BG | |
| #20 30.11.2023 | Line Arrangements | MH | ||
| #21 04.12.2023 | Line Arrangements | MH | ||
| #22 07.12.2023 | Simplicial Depth | Chapter 11 | EW | |
| #23 11.12.2023 | Simplicial Depth | Exercise 10 | EW | |
| #24 14.12.2023 | Simplicial Depth | PS | ||
| #25 18.12.2023 | Simplicial Depth | Exercise 11 | EW | |
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?)
Our 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.
Covered topics include: 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, Crossing Lemma and incidence bounds, arrangements, ham-sandwich cuts, Davenport-Schinzel sequences, 3-SUM hardness, simplicial depth, and Gale Duality.
Every week we provide you with exercises. The students are split into small groups, and the members of each group work together. At the end of the session, for each exercise, a student from a group presents their solution to the rest of the students. In addition to the exercise sessions, we encourage you to solve the exercises in written form and 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 two homework assignments during the semester. The homework is to be solved in written form and 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 two grades will account for 20% 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. The format of this talk will be determined by the number of students who register for the course.
There is an oral exam of 30 minutes during the examination period. Your final grade consists to 60% of the grade for the exam and to 40% 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 oral final exam as detailed above) qualifies for receiving credits.
This course is complemented by a seminar Geometry: Combinatorics & Algorithms in the following spring semester. After having completed the course, it is possible to do a semester, master or diploma thesis in the area. 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.
- Stefan Felsner, Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry, Vieweg, 2004.
- Jiri Matoušek, Lectures on Discrete Geometry, Springer, 2002.
- Takao Nishizeki, Md. Saidur Rahman, Planar Graph Drawing, World Scientific, 2004.
- New to LaTex? Look at Tobias Oetiker's Not So Short Introduction to LaTeX.
- No idea how to run LaTex on your Windows Computer? The usual (La)TeX distribution for Windows is MiKTeX
| Last modified: Thu Jul 6 09:55:17 CEST 2023 |
|
