In this course we will explore a number of topics in discrete geometry (often also called combinatorial geometry). Discrete geometry usually involve finite sets of points, lines, circles, planes, hyperplanes etc. One might ask the following questions: what is the largest number of regions into which n lines can partition the plane? Or n planes the 3-dimensional space? Given n points in the plane, what is the minimum number of distinct distances occurring between them?
Results from discrete geometry are indispensable as a foundation for any serious treatment of computational geometry and combinatorial optimization. In this course we will concentrate on these foundations, that is, on geometric results rather than algorithms. We will put an accent on active problem solving using the techniques we have learnt.
The following is a list of possible topics (but I will add and remove topics during the course):
The class meets Tuesdays and Thursdays from 13:00 to 14:30 in classroom 3444 in the EECS building. Lectures will be given in English. We sometimes have extra meetings to discuss the homework, on Wednesdays at 16:00 in classroom number 3.
Grading will be based on regular homeworks (see below), student participation, and possibly one or two quizzes (during normal class hours).
We will be using material from the following books. It is not necessary that students buy any of these books (if you take notes during the class).
The material covered in the lectures so far (extra Wednesday meetings are indicated in red):
| March 3 | Introduction to discrete geometry, convexity, convex combinations | 1.2 |
| March 8 | Radon's Lemma, Helly's Theorem and applications | 1.3 |
| March 10 | Solutions to homework 1, Center points | 1.4 |
| March 15 | Cancelled | |
| March 17 | Cancelled | |
| March 22 | Solutions to homework 2 | |
| March 24 | Minkowski's Theorem, duality | 2.1, 5.1 |
| March 29 | Duality of sets | 5.1 |
| April 1 | Convex polytopes, equivalence of H- and V- polytopes | 5.2 |
| April 5 | Arbor day | |
| April 6 | Solutions to homework 3 | |
| April 7 | Faces of convex polytopes | 5.3 |
| April 12 | Cyclic polytopes | 5.4 |
| April 13 | Solutions to homework 4 | |
| April 14 | Upper-bound theorem, power diagrams | 5.5, 5.7 |
| April 19 | Incidence problems | 4.1, 4.2 |
| April 21 | Midterm week | |
| April 26 | Midterm week | |
| April 28 | Crossing lemma, proof of Szemeredi-Trotter | 4.3 |
| May 3 | Distinct distances | 4.4 |
| May 4 | Solutions to homework 5 | |
| May 5 | Children's day | |
| May 10 | Proof of Szemeredi-Trotter using cutting lemma | 4.5, 4.6 |
| May 12 | Proof of tight cutting lemma; Introduction to Davenport-Schinzel sequences | 4.7, 7.1 |
| May 17 | Davenport-Schinzel sequences | 7.1, 7.3 |
| May 19 | Lower envelope of rays, single cell in arrangement of line segments; Introduction to Brunn-Minkowski | 12.2 |
| May 24 | Brunn-Minkowski theorem | 12.2 |
| May 25 | Solutions to homework 6 | |
| May 26 | Brunn-Minkowski application: overlap of convex sets | 12.2 |
| May 31 | Guest speaker: Antoine Vigneron Approximating a convex body | |
| June 2 | Partial and linear orders | 12.3 |
| June 7 | Cancelled (SoCG 2005) | |
| June 9 | Cancelled (SoCG 2005) | |
| June 14 | Solutions to homework 7 |
There will be a small homework assignment every week. You will have one week to complete the assignment. Homeworks have to be turned in in English, and must be submitted at the beginning of the lecture (on the day of the deadline). You must be able to explain your solution to a homework during the class.
One homework will be a slightly larger project (and you'll have more time to complete it).
Discussions with your fellow students and with me are encouraged (although it is probably a good idea to spend a few minutes to try to solve each problem by yourself first). Researching on the internet is highly discouraged. In any case, you must write up your solution by yourself, and you must acknowledge all sources used for your solution (webpages, books, discussions with other students).
I believe that it is important that graduate students do not just turn in a stack of papers and expect the professor to tell them what is correct and what isn't, but that they are capable of making an objective judgement themselves. This is especially true in mathematics (and therefore theoretical computer science). After all, a proof is a proof. You will know whether you have solved the problem after you have done it. In this course you will develop your skill in evaluating what you have done. We practice this self-evaluation, as follows:
On the top of the first sheet that you turn in, please put (a) your name and student number, (b) how much time you spent working on the homework, and (c) a little table like the following:
I will maintain your homework score based on this self-evaluation. Of course I will read and check the homeworks that have been turned in, and if I find that your self-judgement was too positive, I will deduct points for that problem.
The homework should take you not more than about three hours per week. I'm asking you to tell me how long you actually spent on it so that I can estimate the degree of difficulty and the workload of the course.