Handbook of Convex Geometry (eBook)

Front Cover 1
Handbook of Convex Geometry 4
Copyright Page 5
Table of Contents 8
Preface 6
List of Contributors 12
CHAPTER 0. History of Convexity 14
1. Introduction 16
2. Antiquity 16
3. Modern times up to the 18th century 17
4. The 19th century with glimpses into the 20th century 18
5. From the 19th to the 20th century and the 20th century 20
Acknowledgements 28
Part 1: Classical Convexity 30
CHAPTER 1.1 Characterizations of Convex Sets 32
1. The classical characterizations 34
2. Characteristic properties of convex sets in analysis and differential geometry 35
3. Topology. Combinatorics 38
4. Extensions of the notion of a convex set. Realizations 42
5. Measures of convexity 45
6. Looking out 46
References 48
CHAPTER 1.2 Mixed Volumes 56
1. Elementary convexity 58
2. Mixed volumes 59
3. Quermassintegrals and intrinsic volumes 62
4. Mixed surface area measures 65
5. Symmetrization 67
6. Fundamental inequalities 70
7. Equality in the Aleksandrov-Fenchel inequality 73
8. Additional inequalities 77
Acknowledgment 79
References 79
CHAPTER 1.3 The Standard Isoperimetric Theorem 86
1. Introduction 88
2. The isoperimetric theorem for the Euclidean plane 92
3. The isoperimetric theorem for the Euclidean n -dimensional space 97
References 133
CHAPTER 1.4 Stability of Geometric Inequalities 138
1. Introduction 140
2. Bonnesen's inequality and its consequences 143
3. The Brunn-Minkowski inequality 146
4. Inequalities for mixed volumes 150
5. Inequalities for the mean projection measures and the isoperimetric inequality 153
6. Cap bodies, bodies of constant width, equichordal sets, packings and coverings 157
7. Projections of convex bodies 159
References 161
CHAPTER 1.5 Selected Affine Isoperimetric Inequalities 164
Introduction 166
1. Inequalities for random simplices in a convex body 166
2. The Busemann-Petty centroid inequality 168
3. The Petty projection inequality 169
4. Petty's affine projection inequality 170
5. Relationship between the Busemann-Petty centroid and Petty projection inequalities 171
6. Relationship between the Busemann-Petty centroid inequality and Petty's affine projection inequality 172
7. The Busemann intersection inequality and its relatives 173
8. Petty's geominimal surface area inequality and its relatives 176
9. The curvature image inequality 177
10. The affine isoperimetric inequality 177
11. The Blaschke-Santaló inequality 178
12. Open problems 180
Acknowledgements 184
References 184
CHAPTER 1.6 Extremum Problems for Convex Discs and Polyhedra 190
1. Introduction and notation 192
2. Some extremum problems for convex discs 194
3. Bounds for the volume of a convex polyhedron 210
4. Surface area and edge-curvature 215
5. Total length of the edges of a polyhedron 218
6. The isoperimetric problem for convex polyhedra 221
Acknowledgement 227
References 227
CHAPTER 1.7 Rigidity 236
1. Introduction 238
2. Early results 239
3. Basic definitions and basic results 245
4. Infinitesimal and static rigidity related to surfaces 253
5. Second-order rigidity and pre-stress stability 269
CHAPTER 1.8 Convex Surfaces, Curvature and Surface Area Measures 286
Introduction 288
1. First order boundary structure of convex bodies 288
2. Pointwise curvatures 292
3. Curvature measures and surface area measures 294
4. Special cases and relations to local shape 297
5. Minkowski's theorem and other existence problems 300
6. Uniqueness and stability results 305
References 309
CHAPTER 1.9 The Space of Convex Bodies 314
1. Introduction 316
2. Lattice structure 316
3. Semigroup structure and embedding 317
4. Metrics 320
5. Topology 323
6. Measure and category 324
7. Entropy and generalized dimension 324
Acknowledgements 325
References 325
CHAPTER 1.10 Aspects of Approximation of Convex Bodies 332
1. Introduction 334
2. Some definitions 334
3. Properties of best approximating polytopes for d = 2 336
4. Upper bounds 337
5. Asymptotic estimates 339
6. Algorithmic and asymptotic step-by-step approximation 345
7. Approximation of special (classes of) convex bodies 347
8. Symmetrization 349
9. Miscellanea 350
Acknowledgements 352
References 352
CHAPTER 1.11 Special Convex Bodies 360
1. Introduction 362
2. Simplices 368
3. Ellipsoids 371
4. Centrally symmetric convex bodies 374
5. Convex bodies of constant width 376
References 381
Part 2: Combinatorial Aspects of Convexity 400
CHAPTER 2.1 Helly, Radon, and Carathéodory Type Theorems 402
1. Introduction 404
PART I. HELLY'S THEOREM, AND THE COMBINATORIAL GEOMETRY OF FAMILIES OF CONVEX SETS 405
2. Helly's Theorem 405
3. Generalizations of Helly's Theorem 408
4. Spherical and topological Helly-type theorems 413
5. Other Helly-type theorems 417
6. Piercing and coloring properties of convex sets 419
7. Common transversals 423
8. Intersection patterns of convex sets 428
PART II. RADON'S AND CARATHÉODORY'S THEOREM, AND THE CONVEXITY PROPERTIES OF CONFIGURATIONS OF POINTS 434
9. Radon's Theorem and its relatives 434
10. The theorems of Carathéodory and Steinitz 443
11. The theorems of Kirchberger and Krasnosel'skii 446
CHAPTER 2.2 Problems in Discrete and Combinatorial Geometry 462
Introduction 464
1. Sets of points and related topics 464
2. Finite tilings of sets 474
Acknowledgements 487
References 487
CHAPTER 2.3 Combinatorial Aspects of Convex Polytopes 498
1. Definitions and fundamental results 500
2. Shellings 501
3. Algebraic methods 509
4. Gale transforms and diagrams 524
5. Graphs of polytopes 533
6. Combinatorial structure 536
References 541
CHAPTER 2.4 Polyhedral Manifolds 548
1. Preliminaries 550
2. Embeddability 553
3. Minimality properties of polyhedra 555
4. Combinatorially regular polyhedra and related topics 558
References 561
CHAPTER 2.5 Oriented Matroids 568
1. Introduction 570
2. Models in oriented matroid theory 581
3. Matroid polytopes 588
4. Matroid theory in convexity 598
5. Polytopes versus matroid polytopes 601
References 605
CHAPTER 2.6 Algebraic Geometry and Convexity 616
1. Introduction and historical notes 618
2. Definition of toric varieties 620
3. Blow ups and stellar subdivisions 625
4. Resolution of singularities 627
5. Invertible sheaves, Picard group, and projective toric varieties 629
6. Homology 632
7. Research problems 634
8. Dictionary 637
References 637
CHAPTER 2.7 Mathematical Programming and Convex Geometry 640
Introduction 642
1. Terminology for convex optimization 643
2. Some qualitative aspects of convex minimization 645
3. Some qualitative aspects of convex maximization 646
4. General background for linear programming 648
5. Duality primal-dual algorithm
6. Fourier-Motzkin elimination 652
7. The simplex method 653
8. Center of gravity cuts and the ellipsoid method 660
9. Karmarkar's protective algorithm 666
10. Analytic center, path-following methods 672
11. Strongly polynomial algorithms 676
Acknowledgement 677
References 677
CHAPTER 2.8 Convexity and Discrete Optimization 688
1. Introduction 690
2. Convex, mixed-integer programming 691
3. Feasibility and computational complexity of integer programs 694
4. Integral polyhedra 695
5. Polyhedral combinatorics 697
6. Combinatorial optimization problems arising from convex geometric configurations 705
References 707
CHAPTER 2.9 Geometric Algorithms 712
1. Introduction 714
2. Topics in computational geometry 716
3. Concluding remarks 742
References 743
Author Index 750
Subject Index 784