Computational Geometry, Easter 2011

When:

Mondays, Wednesdays, Fridays 10am

Where:

MR4, CMS

What:

We shall focus on aspects of computational geometry that require less background in algorithms and data structures, but more mathematical finesse. The topics will include geometric range searching, linear programming, computing volumes of convex bodies.

Resources:

We will not follow a book. The standard introduction to computational geometry is the Computational Geometry: Algorithms and Applications by de Berg, Cheong, van Kreveld and Overmars, which is a great read. Much of geometric background can be found in Lectures on Discrete Geometry by Jiří Matoušek. The survey on volume computation by Béla Bollobás contains some of the material we cover. For geometric range searching the survey by Matoušek is very nice.

Lectures:

Note that there will be no lecture on May 18 due to a One-Day Colloquim in Combinatorics in London.

• April 29: Introduction, Elekes's theorem, darts algorithm. Notes #1.
• May 2: Darts analysis, Ellipsoid method, basic multistage algorithm.
• May 4: Markov chains and conductance.
• May 6: Conductance cont'd, Metropolis chains. Notes #2.
• May 9: Diameter/cut isoperimetric inequality.
• May 11: Diameter/cut isoperimetric inequality II.
• May 13: Diameter/cut isoperimetric inequality III, Brunn--Minkowski theorem.
• May 16: End of volume computations.
• May 18: No lecture.
• May 20: Leftover calculations.
• May 23: Basic range searching. Notes #3.
• May 25: Optimal range searching in dimension 2.