"Lectures on discrete geometry TOC" - читать интересную книгу автора (Matousek J.)

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