Title | Lectures on Discrete Geometry [electronic resource] / edited by Jiลรญ Matouลกek |
---|---|
Imprint | New York, NY : Springer New York, 2002 |
Connect to | http://dx.doi.org/10.1007/978-1-4613-0039-7 |
Descript | XVI, 486 p. online resource |
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 Harn 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?s-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รฉodory 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รกsz 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 ??-Embeddings -- 15.7 Upper Bounds for Euclidean Embeddings -- What Was It About? An Informal Summary -- Hints to Selected Exercises