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