**2005-06-02**- Homework 7 is available. There is no class next week (I'm in Italy), and we will have only one last class on June 14.
**2005-05-16**- With all the excitement about moving my office, I forgot to put homework 6 on the webpage. It is available now, and the deadline has been postponed one week.
**2005-04-21**- Homework 5 is available. Starting from May 4, the extra classes on Wednesday are in classroom number 3!
**2005-04-07**- Homework 4 is available.
**2005-03-29**- Homework 3 is available. Contrary to what I said last week, there will be no extra class this week. The first extra class will be Wednesday, April 6.
**2005-03-10**- Homework 2 is available (see link below). There is no class on March 15 and March 17. The next class is on March 22.
**2005-03-03**- Homework 1 is available (see link below)

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):

- Davenport-Schinzel sequences
- Convexity: Radon, Caratheodory, and Helly theorems
- Convex polytopes, linear programming, the upper-bound theorem
- epsilon-Nets, epsilon-Approximations, Cuttings and Partitionings
- Voronoi and power diagrams
- Topological methods, Ham-Sandwich theorems
- Incidence bounds and the crossing lemma

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).

- Jiri Matousek.
*Lectures on Discrete Geometry*. Springer-Verlag 2002. - Janos Pach and Pankaj Agarwal.
*Combinatorial Geometry*. Wiley-Interscience 1995. - Jiri Matousek.
*Using the Borsuk-Ulam Theorem*. Springer-Verlag 2003.

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:

**P**- ("Perfect") You are very confident that you have a correct proof/solution. This earns you full points.
**S**- ("Solved") You have solved the problem, but aren't quite confident that there may not be some small mistake. This earns you 80% of the points.
**N**- ("Not solved") You worked on the problem, but were not able to solve the problem. This earns you 30% of the points, no matter what and how much you wrote in your solution (you can leave it empty).
**0**- You haven't tried to solve the problem. This earns you no points.

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.

- Homework 1 (due on March 10)
- Homework 2 (due on March 22)
- Homework 3 (due on April 6)
- Homework 4 (due on April 13)
- Homework 5 (due on May 4)
- Homework 6 (due on May 25)
- Homework 7 (due on June 14)

Otfried Cheong