| |
| |
| Preface | |
| |
| |
| Notation and Terminology | |
| |
| |
| |
| Convexity | |
| |
| |
| |
| Linear and Affine Subspaces, General Position | |
| |
| |
| |
| Convex Sets, Convex Combinations, Separation | |
| |
| |
| |
| Radon's Lemma and Helly's Theorem | |
| |
| |
| |
| Centerpoint and Ham Sandwich | |
| |
| |
| |
| Lattices and Minkowski's Theorem | |
| |
| |
| |
| Minkowski's Theorem | |
| |
| |
| |
| General Lattices | |
| |
| |
| |
| An Application in Number Theory | |
| |
| |
| |
| Convex Independent Subsets | |
| |
| |
| |
| The Erdos Szekeres Theorem | |
| |
| |
| |
| Horton Sets | |
| |
| |
| |
| Incidence Problems | |
| |
| |
| |
| Formulation | |
| |
| |
| |
| Lower Bounds: Incidences and Unit Distances | |
| |
| |
| |
| Point-Line Incidences via Crossing Numbers | |
| |
| |
| |
| Distinct Distances via Crossing Numbers | |
| |
| |
| |
| Point-Line Incidences via Cuttings | |
| |
| |
| |
| A Weaker Cutting Lemma | |
| |
| |
| |
| The Cutting Lemma: A Tight Bound | |
| |
| |
| |
| Convex Polytopes | |
| |
| |
| |
| Geometric Duality | |
| |
| |
| |
| H-Polytopes and V-Polytopes | |
| |
| |
| |
| Faces of a Convex Polytope | |
| |
| |
| |
| Many Faces: The Cyclic Polytopes | |
| |
| |
| |
| The Upper Bound Theorem | |
| |
| |
| |
| The Gale Transform | |
| |
| |
| |
| Voronoi Diagrams | |
| |
| |
| |
| Number of Faces in Arrangements | |
| |
| |
| |
| Arrangements of Hyperplanes | |
| |
| |
| |
| Arrangements of Other Geometric Objects | |
| |
| |
| |
| Number of Vertices of Level at Most k | |
| |
| |
| |
| The Zone Theorem | |
| |
| |
| |
| The Cutting Lemma Revisited | |
| |
| |
| |
| Lower Envelopes | |
| |
| |
| |
| Segments and Davenport-Schinzel Sequences | |
| |
| |
| |
| Segments: Superlinear Complexity of the Lower Envelope | |
| |
| |
| |
| More on Davenport-Schinzel Sequences | |
| |
| |
| |
| Towards the Tight Upper Bound for Segments | |
| |
| |
| |
| Up to Higher Dimension: Triangles in Space | |
| |
| |
| |
| Curves in the Plane | |
| |
| |
| |
| Algebraic Surface Patches | |
| |
| |
| |
| Intersection Patterns of Convex Sets | |
| |
| |
| |
| The Fractional Helly Theorem | |
| |
| |
| |
| The Colorful Caratheodory Theorem | |
| |
| |
| |
| Tverberg's Theorem | |
| |
| |
| |
| Geometric Selection Theorems | |
| |
| |
| |
| A Point in Many Simplices: The First Selection Lemma | |
| |
| |
| |
| The Second Selection Lemma | |
| |
| |
| |
| Order Types and the Same-Type Lemma | |
| |
| |
| |
| A Hypergraph Regularity Lemma | |
| |
| |
| |
| A Positive-Fraction Selection Lemma | |
| |
| |
| |
| Transversals and Epsilon Nets | |
| |
| |
| |
| General Preliminaries: Transversals and Matchings | |
| |
| |
| |
| Epsilon Nets and VC-Dimension | |
| |
| |
| |
| Bounding the VC-Dimension and Applications | |
| |
| |
| |
| Weak Epsilon Nets for Convex Sets | |
| |
| |
| |
| The Hadwiger-Debrunner (p,q)-Problem | |
| |
| |
| |
| A (p,q)-Theorem for Hyperplane Transversals | |
| |
| |
| |
| Attempts to Count k-sets | |
| |
| |
| |
| Definitions and First Estimates | |
| |
| |
| |
| Sets with Many Halving Edges | |
| |
| |
| |
| The Lovasz Lemma and Upper Bounds in All Dimensions | |
| |
| |
| |
| A Better Upper Bound in the Plane | |
| |
| |
| |
| Two Applications of High-Dimensional Polytopes | |
| |
| |
| |
| The Weak Perfect Graph Conjecture | |
| |
| |
| |
| The Brunn-Minkowski Inequality | |
| |
| |
| |
| Sorting Partially Ordered Sets | |
| |
| |
| |
| Volumes in High Dimension | |
| |
| |
| |
| Volumes, Paradoxes of High Dimension, and Nets | |
| |
| |
| |
| Hardness of Volume Approximation | |
| |
| |
| |
| Constructing Polytopes of Large Volume | |
| |
| |
| |
| Approximating Convex Bodies by Ellipsoids | |
| |
| |
| |
| Measure Concentration and Almost Spherical Sections | |
| |
| |
| |
| Measure Concentration on the Sphere | |
| |
| |
| |
| Isoperimetric Inequalities and More on Concentration | |
| |
| |
| |
| Concentration of Lipschitz Functions | |
| |
| |
| |
| Almost Spherical Sections: The First Steps | |
| |
| |
| |
| Many Faces of Symmetric Polytopes | |
| |
| |
| |
| Dvoretzky's Theorem | |
| |
| |
| |
| Embedding Finite Metric Spaces into Normed Spaces | |
| |
| |
| |
| Introduction: Approximate Emboddings | |
| |
| |
| |
| The Johnson-Lindenstrauss Flattening Lemma | |
| |
| |
| |
| Lower Bounds by Counting | |
| |
| |
| |
| A Lower Bound for the Hamming Cube | |
| |
| |
| |
| A Tight Lower Bound via Expanders | |
| |
| |
| |
| Upper Bounds for l[subscript [infinity]]-Embeddings | |
| |
| |
| |
| Upper Bounds for Euclidean Embeddings | |
| |
| |
| What Was It About? An Informal Summary | |
| |
| |
| Hints to Selected Exercises | |
| |
| |
| Bibliography | |
| |
| |
| Index | |