| Preface | |
| Notation and Terminology | |
| Convexity | p. 1 |
| Linear and Affine Subspaces, General Position | p. 1 |
| Convex Sets, Convex Combinations, Separation | p. 5 |
| Radon's Lemma and Helly's Theorem | p. 9 |
| Centerpoint and Ham Sandwich | p. 14 |
| Lattices and Minkowski's Theorem | p. 17 |
| Minkowski's Theorem | p. 17 |
| General Lattices | p. 21 |
| An Application in Number Theory | p. 27 |
| Convex Independent Subsets | p. 29 |
| The Erdos Szekeres Theorem | p. 30 |
| Horton Sets | p. 34 |
| Incidence Problems | p. 41 |
| Formulation | p. 41 |
| Lower Bounds: Incidences and Unit Distances | p. 51 |
| Point-Line Incidences via Crossing Numbers | p. 54 |
| Distinct Distances via Crossing Numbers | p. 59 |
| Point-Line Incidences via Cuttings | p. 64 |
| A Weaker Cutting Lemma | p. 70 |
| The Cutting Lemma: A Tight Bound | p. 73 |
| Convex Polytopes | p. 77 |
| Geometric Duality | p. 78 |
| H-Polytopes and V-Polytopes | p. 82 |
| Faces of a Convex Polytope | p. 86 |
| Many Faces: The Cyclic Polytopes | p. 96 |
| The Upper Bound Theorem | p. 100 |
| The Gale Transform | p. 107 |
| Voronoi Diagrams | p. 115 |
| Number of Faces in Arrangements | p. 125 |
| Arrangements of Hyperplanes | p. 126 |
| Arrangements of Other Geometric Objects | p. 130 |
| Number of Vertices of Level at Most k | p. 140 |
| The Zone Theorem | p. 146 |
| The Cutting Lemma Revisited | p. 152 |
| Lower Envelopes | p. 165 |
| Segments and Davenport-Schinzel Sequences | p. 165 |
| Segments: Superlinear Complexity of the Lower Envelope | p. 169 |
| More on Davenport-Schinzel Sequences | p. 173 |
| Towards the Tight Upper Bound for Segments | p. 178 |
| Up to Higher Dimension: Triangles in Space | p. 182 |
| Curves in the Plane | p. 186 |
| Algebraic Surface Patches | p. 189 |
| Intersection Patterns of Convex Sets | p. 195 |
| The Fractional Helly Theorem | p. 195 |
| The Colorful Caratheodory Theorem | p. 198 |
| Tverberg's Theorem | p. 200 |
| Geometric Selection Theorems | p. 207 |
| A Point in Many Simplices: The First Selection Lemma | p. 207 |
| The Second Selection Lemma | p. 210 |
| Order Types and the Same-Type Lemma | p. 215 |
| A Hypergraph Regularity Lemma | p. 223 |
| A Positive-Fraction Selection Lemma | p. 228 |
| Transversals and Epsilon Nets | p. 231 |
| General Preliminaries: Transversals and Matchings | p. 231 |
| Epsilon Nets and VC-Dimension | p. 237 |
| Bounding the VC-Dimension and Applications | p. 243 |
| Weak Epsilon Nets for Convex Sets | p. 251 |
| The Hadwiger-Debrunner (p,q)-Problem | p. 255 |
| A (p,q)-Theorem for Hyperplane Transversals | p. 259 |
| Attempts to Count k-sets | p. 265 |
| Definitions and First Estimates | p. 265 |
| Sets with Many Halving Edges | p. 273 |
| The Lovasz Lemma and Upper Bounds in All Dimensions | p. 277 |
| A Better Upper Bound in the Plane | p. 283 |
| Two Applications of High-Dimensional Polytopes | p. 289 |
| The Weak Perfect Graph Conjecture | p. 290 |
| The Brunn-Minkowski Inequality | p. 296 |
| Sorting Partially Ordered Sets | p. 302 |
| Volumes in High Dimension | p. 311 |
| Volumes, Paradoxes of High Dimension, and Nets | p. 311 |
| Hardness of Volume Approximation | p. 315 |
| Constructing Polytopes of Large Volume | p. 322 |
| Approximating Convex Bodies by Ellipsoids | p. 324 |
| Measure Concentration and Almost Spherical Sections | p. 329 |
| Measure Concentration on the Sphere | p. 330 |
| Isoperimetric Inequalities and More on Concentration | p. 333 |
| Concentration of Lipschitz Functions | p. 337 |
| Almost Spherical Sections: The First Steps | p. 341 |
| Many Faces of Symmetric Polytopes | p. 347 |
| Dvoretzky's Theorem | p. 348 |
| Embedding Finite Metric Spaces into Normed Spaces | p. 355 |
| Introduction: Approximate Emboddings | p. 355 |
| The Johnson-Lindenstrauss Flattening Lemma | p. 358 |
| Lower Bounds by Counting | p. 362 |
| A Lower Bound for the Hamming Cube | p. 369 |
| A Tight Lower Bound via Expanders | p. 373 |
| Upper Bounds for l[subscript [infinity]]-Embeddings | p. 385 |
| Upper Bounds for Euclidean Embeddings | p. 389 |
| What Was It About? An Informal Summary | p. 401 |
| Hints to Selected Exercises | p. 409 |
| Bibliography | p. 417 |
| Index | p. 459 |
| Table of Contents provided by Blackwell. All Rights Reserved. |
