preface
notation and terminology
1 convexity
1.1 linear and affine subspaces, general position
1.2 convex sets, convex combinations, separation
1.3 radon's lemma and helly's theorem
1.4 centerpoint and ham sandwich
2 lattices and minkowski's theorem
2.1 minkowski's theorem
2.2 general lattices
2.3 an application in number theory
3 convex independent subsets
3.1 the erdos-szekeres theorem
3.2 horton sets
4 incidence problems

preface
notation and terminology
1 convexity
1.1 linear and affine subspaces, general position
1.2 convex sets, convex combinations, separation
1.3 radon's lemma and helly's theorem
1.4 centerpoint and ham sandwich
2 lattices and minkowski's theorem
2.1 minkowski's theorem
2.2 general lattices
2.3 an application in number theory
3 convex independent subsets
3.1 the erdos-szekeres theorem
3.2 horton sets
4 incidence problems
4.1 formulation
4.2 lower bounds: incidences and unit distances.
4.3 point-line incidences via crossing numbers
4.4 distinct distances via crossing numbers

.4.5 point-line incidences via cuttings
4.6 a weaker cutting lemma
4.7 the cutting lemma: a tight bound
5 convex polytopes
5.1 geometric duality
5.2 h-polytopes and v-polytopes
5.3 faces of a convex polytope
5.4 many faces: the cyclic polytopes
5.5 the upper bound theorem
5.6 the gale transform
5.7 voronoi diagrams
6 number of faces in arrangements
6.1 arrangements of hyperplanes
6.2 arrangements of other geometric objects
6.3 number of vertices of level at most k
6.4 the zone theorem
6.5 the cutting lemma revisited
7 lower envelopes
7.1 segments and davenport-schinzel sequences
7.2 segments: superlinear complexity of the lower envelope.
7.3 more on davenport-schinzel sequences
7.4 towards the tight upper bound for segments
7.5 up to higher dimension: triangles in space
7.6 curves in the plane
7.7 algebraic surface patches
8 intersection patterns of convex sets
8.1 the fractional helly theorem
8.2 the colorful carath~odory theorem
8.3 tverberg's theorem
9 geometric selection theorems
9.1 a point in many simplices: the first selection lemma
9.2 the second selection lemma
9.3 order types and the same-type lemma
9.4 a hypergraph regularity lemma
9.5 a positive-fraction selection lemma
10 transversals and epsilon nets
10.1 general preliminaries: transversals and matchings
10.2 epsilon nets and vc-dimension
10.3 bounding the vc-dimension and applications
10.4 weak epsilon nets for convex sets
10.5 the hadwiger-debrunner (p, q)-problem
10.6 a (p, q)-theorem for hyperplane transversals
11 attempts to count k-sets
11.1 definitions and first estimates
11.2 sets with many halving edges
11.3 the lovfisz lemma and upper bounds in all dimensions
11.4 a better upper bound in the plane
12 two applications of high-dimensional polytopes
12.1 the weak perfect graph conjecture
12.2 the brunn-minkowski inequality
12.3 sorting partially ordered sets
13 volumes in high dimension
13.1 volumes, paradoxes of high dimension, and nets
13.2 hardness of volume approximation
13.3 constructing polytopes of large volume
13.4 approximating convex bodies by ellipsoids
14 measure concentration and almost spherical sections
14.1 measure concentration on the sphere
14.2 isoperimetric inequalities and more on concentration
14.3 concentration of lipschitz functions
14.4 almost spherical sections: the first steps
14.5 many faces of symmetric polytopes
14.6 dvoretzky's theorem
15 embedding finite metric spaces into normed spaces
15.1 introduction: approximate embeddings
15.2 the johnson-lindenstranss flattening lemma
15.3 lower bounds by counting
15.4 a lower bound for the hamming cube
15.5 a tight lower bound via expanders
15.6 upper bounds for ~oo-embeddings
15.7 upper bounds for euclidean embeddings
what was it about? an informal summary
hints to selected exercises
bibliography
index