Contemporary Mathematics
Volume: 453;
2008;
556 pp;
Softcover
MSC: Primary 01; 05; 14; 51; 52; 55; 68;
Print ISBN: 978-0-8218-4239-3
Product Code: CONM/453
List Price: $133.00
AMS Member Price: $106.40
MAA Member Price: $119.70
Electronic ISBN: 978-0-8218-8132-3
Product Code: CONM/453.E
List Price: $133.00
AMS Member Price: $106.40
MAA Member Price: $119.70
You may also like
Surveys on Discrete and Computational Geometry: Twenty Years Later
Share this pageEdited by Jacob E. Goodman; János Pach; Richard Pollack
This volume contains nineteen survey papers describing the state of
current research in discrete and computational geometry as well as a
set of open problems presented at the 2006 AMS-IMS-SIAM Summer
Research Conference "Discrete and Computational Geometry—Twenty
Years Later", held in Snowbird, Utah, in June 2006. Topics surveyed
include metric graph theory, lattice polytopes, the combinatorial
complexity of unions of geometric objects, line and pseudoline
arrangements, algorithmic semialgebraic geometry, persistent homology,
unfolding polyhedra, pseudo-triangulations, nonlinear computational
geometry, \(k\)-sets, and the computational complexity of
convex bodies.
Discrete and computational geometry originated as a discipline in the
mid-1980s when mathematicians in the well-established field of discrete
geometry and computer scientists in the (then) nascent field of
computational geometry began working together on problems of common
interest. The combined field has experienced a huge growth in the past
twenty years, which the present volume attests to.
Readership
Graduate students and research mathematicians interested in discrete and computational geometry.
Table of Contents
Surveys on Discrete and Computational Geometry: Twenty Years Later
- Contents v6 free
- Preface vii8 free
- Musings on discrete geometry and "20 years of Discrete & Computational Geometry" 110 free
- State of the union (of geometric objects) 918
- Metric graph theory and geometry: a survey 4958
- Extremal problems for convex lattice polytopes: a survey 8796
- On simple arrangements of lines and pseudo-lines in P2 and R2 with the maximum number of triangles 105114
- The computational complexity of convex bodies 117126
- Algorithmic semi-algebraic geometry and topology – recent progress and open problems 139148
- 1. Introduction 139148
- 2. Semi-algebraic Geometry: Background 141150
- 3. Recent Algorithmic Results 148157
- 4. Algorithmic Preliminaries 150159
- 5. Topological Preliminaries 160169
- 6. Algorithms for Computing the First Few Betti Numbers 180189
- 7. The Quadratic Case 192201
- 8. Betti Numbers of Arrangements 205214
- 9. Open Problems 208217
- Acknowledgment 209218
- References 209218
- Expansive motions 213222
- All polygons flip finitely … right? 231240
- Persistent homology—a survey 257266
- Recent progress on line transversals to families of translated ovals 283292
- An improved, simple construction of many halving edges 299308
- Unfolding orthogonal polyhedra 307316
- The discharging method in combinatorial geometry and the Pach-Sharir conjecture 319328
- Pseudo-triangulations—a survey 343352
- 1. Introduction 344353
- 2. Basic Properties of Pseudo-Triangulations 346355
- 3. The Set of all Pseudo-Triangulations 355364
- 4. 3D Liftings and Locally Convex Functions 364373
- 5. Self-Stresses, Reciprocal Diagrams, and the Maxwell-Cremona Correspondence 372381
- 6. Pseudo-Triangulations and Rigidity 377386
- 7. Planar Rigid Graphs are Pseudo-Triangulations 384393
- 8. Polytopes of Pseudo-Triangulations 391400
- 9. Applications of Pseudo-Triangulations 397406
- References 407416
- Line problems in nonlinear computational geometry 411420
- On empty hexagons 433442
- k-sets and k-facets 443452
- 1. Introduction 444453
- 2. Preliminaries 458467
- 3. Random Sampling 467476
- 4. Special Point Sets 470479
- 5. Lower Bounds 473482
- 6. Upper Bounds for Halving Facets in All Dimensions 477486
- 7. Crossings in Dimension 2. 482491
- 8. Improvements in Three And Four Dimensions 487496
- 9. Convex Quadrilaterals 491500
- 10. Connections to the Combinatorial Theory of Convex Polytopes 496505
- References 507516
- An Erdős-Szekeres type problem for interior points 515524
- The kissing number, blocking number and covering number of a convex body 529538
- Open problems 549558