Topics in Computation Theory (CS700)

Discrete Geometry

Spring Semester 2005


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.
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.
Homework 5 is available. Starting from May 4, the extra classes on Wednesday are in classroom number 3!
Homework 4 is available.
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.
Homework 2 is available (see link below). There is no class on March 15 and March 17. The next class is on March 22.
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):


Otfried Cheong. Office: E3-1 3434, Phone: 3542.


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.


CS604 Computational Geometry (the prerequisite can be waived, especially for Math students).


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

Course progress

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:

Example of homework table

The left column is the number of the problem, in the right column you indicate your solution. There are four values you can fill in:
("Perfect") You are very confident that you have a correct proof/solution. This earns you full points.
("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.
("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).
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.

Otfried Cheong