LECTURES ON DISCRETE GEOMETRY (Jiri Matousek)

errata

This page contains, among others, several sample chapters in postscript. Comments are still greatly appreciated, for the errata and possible future editions (mistakes, missing references, passages that are confusing or difficult to understand...).
 

from the preface  (html)

table of contents  (text)

informal summary

Chapters

1. basic convexity
2. Minkowski on lattices
3. convex independence in the plane
4. incidence problems
5. convex polytopes
6. number of faces in arrangements
7. lower envelopes, Davenport-Schinzel sequences
8. Tverberg's theorem, fractional Helly's theorem, colorful Caratheodory theorem
9. geometric selection theorems
10. transversals, epsilon-nets, the (p,q)-theorem
11. counting k-sets
12. weak perfect graph conjecture, Brunn-Minkowski inequality and sorting posets
13. high-dimensional convex bodies and volumes, hardness of volume approximation, John's lemma
14. measure concentration, almost spherical sections, many faces of symmetric polytopes, Dvoretzky's theorem
15. embedding finite metric spaces into Euclidean spaces. This is actually a revised and expanded version of the chapter prepared in September 2005 (for a Japanese edition). It reflects some of the exciting developments in the field in 2002-2005.