Lectures on Discrete GeometrySpringer Science & Business Media, 2 mai 2002 - 486 pages This book is primarily a textbook introduction to various areas of discrete geometry. In each area, it explains several key results and methods, in an accessible and concrete manner. It also contains more advanced material in separate sections and thus it can serve as a collection of surveys in several narrower subfields. The main topics include: basics on convex sets, convex polytopes, and hyperplane arrangements; combinatorial complexity of geometric configurations; intersection patterns and transversals of convex sets; geometric Ramsey-type results; polyhedral combinatorics and high-dimensional convexity; and lastly, embeddings of finite metric spaces into normed spaces. |
Table des matières
Convexity | 1 |
12 Convex Sets Convex Combinations Separation | 5 |
13 Radons Lemma and Hellys Theorem | 9 |
14 Centerpoint and Ham Sandwich | 14 |
Lattices and MinkowskTs Theorem | 17 |
22 General Lattices | 21 |
23 An Application in Number Theory | 27 |
Convex Independent Subsets | 29 |
92 The Second Selection Lemma | 210 |
93 Order Types and the SameType Lemma | 215 |
94 A Hypergraph Regularity Lemma | 223 |
95 A PositiveFraction Selection Lemma | 228 |
Transversals and Epsilon Nets | 231 |
102 Epsilon Nets and VCDimension | 237 |
103 Bounding the VCDimension and Applications | 243 |
104 Weak Epsilon Nets for Convex Sets | 251 |
31 The ErdosSzekeres Theorem | 30 |
32 Horton Sets | 34 |
Incidence Problems | 41 |
Incidences and Unit Distances | 51 |
43 PointLine Incidences via Crossing Numbers | 54 |
44 Distinct Distances via Crossing Numbers | 59 |
45 PointLine Incidences via Cuttings | 64 |
46 A Weaker Cutting Lemma | 70 |
A Tight Bound | 73 |
Convex Polytopes | 77 |
51 Geometric Duality | 78 |
52 HPolytopes and VPolytopes | 82 |
53 Faces of a Convex Polytope | 86 |
The Cyclic Polytopes | 96 |
55 The Upper Bound Theorem | 100 |
56 The Gale Transform | 107 |
57 Voronoi Diagrams | 115 |
Number of Faces in Arrangements | 125 |
61 Arrangements of Hyperplanes | 126 |
62 Arrangements of Other Geometric Objects | 130 |
63 Number of Vertices of Level at Most k | 140 |
64 The Zone Theorem | 146 |
65 The Cutting Lemma Revisited | 152 |
Lower Envelopes | 165 |
Superlinear Complexity of the Lower Envelope | 169 |
73 More on DavenportSchinzel Sequences | 173 |
74 Towards the Tight Upper Bound for Segments | 178 |
Triangles in Space | 182 |
76 Curves in the Plane | 186 |
77 Algebraic Surface Patches | 189 |
Intersection Patterns of Convex Sets | 195 |
82 The Colorful Caratheodory Theorem | 198 |
83 Tverbergs Theorem | 200 |
Geometric Selection Theorems | 207 |
105 The HadwigerDebrunner p qrProblem | 255 |
106 A p qTheorem for Hyperplane Transversals | 259 |
Attempts to Count fcSets | 265 |
112 Sets with Many Halving Edges | 273 |
113 The Lovasz Lemma and Upper Bounds in All Dimensions | 277 |
114 A Better Upper Bound in the Plane | 283 |
Two Applications of HighDimensional Polytopes | 289 |
121 The Weak Perfect Graph Conjecture | 290 |
122 The BrunnMinkowski Inequality | 296 |
123 Sorting Partially Ordered Sets | 302 |
Volumes in High Dimension | 311 |
132 Hardness of Volume Approximation | 315 |
133 Constructing Polytopes of Large Volume | 322 |
134 Approximating Convex Bodies by Ellipsoids | 324 |
Measure Concentration and Almost Spherical Sections | 329 |
141 Measure Concentration on the Sphere | 330 |
142 Isoperimetric Inequalities and More on Concentration | 333 |
143 Concentration of Lipschitz Functions | 337 |
The First Steps | 341 |
145 Many Faces of Symmetric Polytopes | 347 |
146 Dvoretzkys Theorem | 348 |
Embedding Finite Metric Spaces into Normed Spaces | 355 |
152 The JohnsonLindenstrauss Flattening Lemma | 358 |
153 Lower Bounds By Counting | 362 |
154 A Lower Bound for the Hamming Cube | 369 |
155 A Tight Lower Bound via Expanders | 373 |
156 Upper Bounds for looEmbeddings | 385 |
157 Upper Bounds for Euclidean Embeddings | 389 |
What Was It About? An Informal Summary | 401 |
Hints to Selected Exercises | 409 |
Bibliography | 417 |
Index | 459 |
Autres éditions - Tout afficher
Expressions et termes fréquents
affine affine hull algebraic algorithm arrangement ball Bibliography and remarks cells combinatorial complexity Comput consider constant construction contains convex body convex hull convex independent convex polytope convex sets coordinates crossing number cube curves cutting lemma d-dimensional Davenport-Schinzel sequences define denote dimension disjoint distance embedding Erdős Euclidean example Exercise exists ɛ-net finite set fixed function Gale transform geometric graph G half-spaces halving edges Helly's theorem hypergraph induction inequality integer intersection lattice least linear lines Lovász lower bound lower envelope matrix metric space Minkowski's theorem n-point set number of edges number of vertices obtained oriented matroid pairs planar planar graph plane point set polynomial position problem proof Proposition proved pseudolines Radon's lemma random Rd+1 real numbers result Section segments selection lemma set system sets in Rd Sharir subset subspace suitable Theory total number transversal triangles Tverberg upper bound VC-dimension vectors vertex set Voronoi diagram
Fréquemment cités
Page 438 - Coding of an information source having ambiguous alphabet and the entropy of graphs, in "Transactions of the 6th Prague Conference on Information Theory, etc.," 1971, Academia, Prague, (1973), 411-425.
Page 424 - B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink. Computing a face in an arrangement of line segments and related problems.
Page 429 - H. Edelsbrunner, L. Guibas and M. Sharir, The complexity of many cells in arrangements of planes and related problems, Discrete Comput.
Page 439 - J. Komlos and M. Simonovits. Szemeredi's regularity lemma and its applications in graph theory. In D. Miklos et al. editors, Combinatorics, Paul Erdos Is Eighty., Vol.
Page 424 - JD Boissonnat, M. Sharir, B. Tagansky and M. Yvinec, Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Discrete Comput.