Lectures on Discrete GeometrySpringer Science & Business Media, 1 déc. 2013 - 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
Lattices and Minkowskis Theorem | 17 |
Convex Independent Subsets | 29 |
Incidence Problems | 41 |
Convex Polytopes | 77 |
Number of Faces in Arrangements | 125 |
Lower Envelopes 165 | 164 |
Intersection Patterns of Convex Sets | 195 |
Geometric Selection Theorems | 207 |
Two Applications of HighDimensional Polytopes | 289 |
Volumes in High Dimension | 311 |
Measure Concentration and Almost Spherical Sections | 329 |
Embedding Finite Metric Spaces into Normed Spaces 355 | 354 |
What Was It About? An Informal Summary | 401 |
Hints to Selected Exercises | 409 |
Bibliography | 417 |
Index 459 | 458 |
Autres éditions - Tout afficher
Expressions et termes fréquents
affine affine hull algebraic algorithm arrangement ball Bibliography and remarks cells combinatorial complexity 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 function Gale transform Geom geometric graph G half-spaces halving edges Helly's theorem hypergraph induction inequality integer intersection lattice least linear linear subspace lines Lovász lower bound lower envelope matrix metric space n-point set number of edges number of vertices obtained oriented matroid Pach pairs planar planar graph plane point set polynomial position problem proof Proposition proved pseudolines Radon's lemma random 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