LECTURES ON DISCRETE GEOMETRY (Jiri Matousek)

errata

The book appeared in April 2002 as volume 212 of the Springer GTM Series. (Here is a publisher's page about it.)

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.
For a survey on the topics of Chapter 15 also see a handbook chapter by Piotr Indyk and me. Many open problems, with updates on recent progress, are listed in Open problems on embeddings of finite metric spaces edited by me.