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 Erd os­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´eodory 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 Lov´asz 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­Lindenstrauss 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 l2-Embeddings 15.7 Upper Bounds for Euclidean Embeddings What Was It About? An Informal Summary Hints to Selected Exercises Bibliography Index