Discrete Geometry (251-0440-00) - SoSe 07
Time & Place
- Lectures : Thursday, 9:15-11:00 @ CAB H52.
- Exercises : Thursday, 11:10-11:55 @ CAB H52.
Instructors
- Lecturers:
Uli Wagner, CAB G33.2/ Tel: (044) 632-7339, e-mail: Jiří Matoušek - Assistant:
Andreas Razen, CAB G37.1/ Tel: (044) 632-7422. e-mail: arazen@inf.ethz.ch
Course Description
Discrete geometry investigates combinatorial properties of configurations of geometric objects. Often, the objects themselves are simple and well-understood, such as points, lines, circles, planes, etc., and interesting problems and questions arise because of the complexity of their interaction. Here are three sample questions:
1) What is the maximum number of regions into which n lines can partition the (Euclidean) plane?
2) What is the maximum number of incidences between n points and n lines in the plane?
3) What is the minimum number of distinct pairwise distances determined by n points in the plane?The first question is easy; the second one is considerably more difficult, but the answer is known (at least asymptotically). The third one is an open question.
Many questions and problems in discrete geometry are easy to understand and interesting for their own sake. Some of them, such as the structure and complexity of convex polytopes, have a long history. Other questions are motivated by other areas of mathematics and computer science, such as combinatorics, computational geometry, or combinatorial optimization.
In terms of keywords, this course will cover (at least a hopefully large subset of) the following topics:
basics on convex sets, convex polytopes, and hyperplane arrangements; combinatorial complexity of geometric configurations; intersection patterns and transversals of convex sets; geometric Ramsey-type results; polyhedral combinatorics and high-dimensional convexity.
Grading
The final grade for this course will be partly based on an oral exam and partly on the total score attained for submitting solutions to the exercises (see below), both equally contributing 50% to the final grade.
The oral exam will take place during the examination period in fall 2007 and last 30 minutes.
The grade 6.0 for the exercises will be given to those who score at least 70% out of all possible points. In order to get a 4.0 you are required to get at least a score of 25% out of all points.
Language
English
Exercises
Each week we will hand out a set of problems that you are requested to work on and to submit your solutions in writing. You may work on the exercises alone or in small groups, but we ask that every student writes up the solutions her- or himself.
For each problem, there will be a certain maximum score of points. For solutions submitted within the first week after the problems have been handed out, you can achieve 100% of this maximum score (if your solutions are complete and correct).
In the following week, we will provide hints on how to solve the exercises from the previous week, and you may continue to work on the problems and submit your written solutions. However, for solutions handed in after the hints have been given, you will receive at most 70% of the maximum score.
Two weeks after a problem set has been handed out, the solutions will be discussed in the exercise session. After that, you may still hand in your own write-up of the solutions, but you get at most 30% of the initial maximal score.
Literature
The course will be based upon the following textbook:- Jiří Matoušek: Lectures on Discrete Geometry, Springer, 2002.
- Günter Ziegler: Lectures on Polytopes, Springer, 1995;
- János Pach, Pankaj K. Agarwal: Combinatorial Geometry, Wiley, 1995;
- Keith M. Ball: An Elementary Introduction to Modern Convex Geometry, available electronically: [PDF];
- Oded Regev: Lecture on "Lattices in Computer Science": course webpage.
- Jacob E. Goodman, Joseph O'Rourke: Handbook of discrete and computational geometry, Chapman & Hall, 2004;
- J.-R. Sack, J. Urrutia: Handbook of computational geometry, North Holland, 2000.
