1 Convexity 1
1.1 Linear and Affine Subspaces,General Position 1
1.2 Convex Sets,Convex Combinations,Separation 5
1.3 Radon's Lemma and Helly's Theorem 9
1.4 Centerpoint and Ham Sandwich 14
2 Lattices and Minkowski's Theorem 17
2.1 Minkowski's Theorem 17
2.2 General Lattices 21
2.3 An Application in Number Theory 27
3 Convex Independent Subsets 29
3.1 The Erd？s-Szekeres Theorem 30
3.2 Horton Sets 34
4 Incidence Problems 41
4.1 Formulation 41
4.2 Lower Bounds:Incidences and Unit Distances 51
4.3 Point-Line Incidences via Crossing Numbers 54
4.4 Distinct Distances via Crossing Numbers 59
4.5 Point-Line Incidences via Cuttings 64
4.6 A Weaker Cutting Lemma 70
4.7 The Cutting Lemma:A Tight Bound 73
5 Convex Polytopes 77
5.1 Geometric Duality 78
5.2 H-Polytopes and V-Polytopes 82
5.3 Faces of a Convex Polytope 86
5.4 Many Faces:The Cyclic Polytopes 96
5.5 The Upper Bound Theorem 100
5.6 The Gale Transform 107
5.7 Voronoi Diagrams 115
6 Number of Faces in Arrangements 125
6.1 Arrangements of Hyperplanes 126
6.2 Arrangements of Other Geometric Objects 130
6.3 Number of Vertices of Level at Most k 140
6.4 The Zone Theorem 146
6.5 The Cutting Lemma Revisited 152
7 Lower Envelopes 165
7.1 Segments and Davenport-Schinzel Sequences 165
7.2 Segments:Superlinear Complexity of the Lower Envelope 169
7.3 More on Davenport-Schinzel Sequences 173
7.4 Towards the Tight Upper Bound for Segments 178
7.5 Up to Higher Dimension:Triangles in Space 182
7.6 Curves in the Plane 186
7.7 Algebraic Surface Patches 189
8 Intersection Patterns of Convex Sets 195
8.1 The Fractional Helly Theorem 195
8.2 The Colorful Carathéodory Theorem 198
8.3 Tverberg's Theorem 200
9 Geometric Selection Theorems 207
9.1 A Point in Many Simplices:The First Selection Lemma 207
9.2 The Second Selection Lemma 210
9.3 Order Types and the Same-Type Lemma 215
9.4 A Hypergraph Regularity Lemma 223
9.5 A Positive-Fraction Selection Lemma 228
10 Transversals and Epsilon Nets 231
10.1 General Preliminaries:Transversals and Matchings 231
10.2 Epsilon Nets and VC-Dimension 237
10.3 Bounding the VC-Dimension and Applications 243
10.4 Weak Epsilon Nets for Convex Sets 251
10.5 The Hadwiger-Debrunner(p,q)-Problem 255
10.6 A(p,q)-Theorem for Hyperplane Transversals 259
11 Attempts to Count k-Sets 265
11.1 Definitions and First Estimates 265
11.2 Sets with Many Halving Edges 273
11.3 The Lovász Lemma and Upper Bounds in All Dimensions 277
11.4 A Better Upper Bound in the Plane 283
12 Two Applications of High-Dimensional Polytopes 289
12.1 The Weak Perfect Graph Conjecture 290
12.2 The Brunn-Minkowski Inequality 296
12.3 Sorting Partially Ordered Sets 302
13 Volumes in High Dimension 311
13.1 Volumes,Paradoxes of High Dimension,and Nets 311
13.2 Hardness of Volume Approximation 315
13.3 Constructing Polytopes of Large Volume 322
13.4 Approximating Convex Bodies by Ellipsoids 324
14 Measure Concentration and Almost Spherical Sections 329
14.1 Measure Concentration on the Sphere 330
14.2 Isoperimetric Inequalities and More on Concentration 333
14.3 Concentration of Lipschitz Functions 337
14.4 Almost Spherical Sections:The First Steps 341
14.5 Many Faces of Symmetric Polytopes 347
14.6 Dvoretzky's Theorem 348
15 Embedding Finite Metric Spaces into Normed Spaces 355
15.1 Introduction:Approximate Embeddings 355
15.2 The Johnson-Lindenstrauss Flattening Lemma 358
15.3 Lower Bounds By Counting 362
15.4 A Lower Bound for the Hamming Cube 369
15.5 A Tight Lower Bound via Expanders 373
15.6 Upper Bounds for ？∞-Embeddings 385
15.7 Upper Bounds for Euclidean Embeddings 389
What Was It About?An Informal Summary 401
Hints to Selected Exercises 409
Bibliography 417
Index 459