Title | New Trends in Discrete and Computational Geometry [electronic resource] / edited by Jรกnos Pach |
---|---|
Imprint | Berlin, Heidelberg : Springer Berlin Heidelberg, 1993 |
Connect to | http://dx.doi.org/10.1007/978-3-642-58043-7 |
Descript | XI, 340 p. 9 illus. online resource |
I. Combinatorics and Algorithms of Arrangements -- 1. Introduction -- 2. Arrangements of Curves in the Plane -- 3. Lower Envelopes and Davenport-Schinzel Sequences -- 4. Faces in Arrangements -- 5. Arrangements in Higher Dimensions -- 6. Summary -- References -- II. Backwards Analysis of Randomized Geometric Algorithms -- 1. Introduction -- 2. Delaunay Triangulations of Convex Polygons -- 3. Intersecting Line Segments -- 4. Constructing Planar Convex Hulls -- 5. Backwards Analysis of QUICKSORT -- 6. A Bad Example -- 7. Linear Programming for Small Dimension -- 8. Welzlโs Minidisk Algorithm -- 9. Clarksonโs Backwards Analysis of the Conflict Graph Based on the Convex Hull Algorithm -- 10. Odds and Ends -- References -- III. Epsilon-Nets and Computational Geometry -- 1. Range Spaces and ?-Nets -- 2. Geometric Range Spaces -- 3. A Sample of Applications -- 4. Removing Logarithms -- 5. Removing the Randomization -- References -- IV. Complexity of Polytope Volume Computation -- 1. Jumps of the Derivatives -- 2. Exact Volume Computation is Hard -- 3. Volume Approximation -- References -- V. Allowable Sequences and Order Types in Discrete and Computational Geometry -- 1. Introduction -- 2. Combinatorial Types of Configurations in the Plane and Allowable Sequences -- 3. Arrangements of Lines and Pseudolines -- 4. Applications of Allowable Sequences -- 5. Order Types of Points in Rd and โGeometric Sortingโ -- 6. The Number of Order Types in Rd -- 7. Isotopy and Realizability Questions -- 8. Lattice Realization of Order Types and the Problem of Robustness in Computational Geometry -- References -- VI. Hyperplane Approximation and Related Topics -- 1. Introduction -- 2. MINSUM Problem: Orthogonal L1-Fit -- 3. MINSUM Problem: Vertical L1-Fit -- 4. MINMAX Problem: Orthogonal L?-Fit -- 5. MINMAX Problem: Vertical L?-Fit -- 6. Related Issues -- References -- VII. Geometric Transversal Theory -- 1. Introduction -- 2. Hadwiger-Type Theorems -- 3. The Combinatorial Complexity of the Space of Transversals -- 4. Translates of a Convex Set -- 5. Transversal Algorithms -- 6. Other Directions -- References -- VIII. Hadwiger-Leviโs Covering Problem Revisited -- 0. Introduction -- 1. On I0(K) and I?(K) -- 2. On Il(K) and k-fold Illumination -- 3. Some Simple Remarks on H(B) -- 4. On Convex Bodies with Finitely Many Corner Points -- 5. Solution of Hadwiger-Leviโs Covering Problem for Convex Polyhedra with Affine Symmetry -- References -- IX. Geometric and Combinatorial Applications of Borsukโs Theorem -- 1. Introduction -- 2. Van Kampen-Flores Type Results -- 3. The Ham-Sandwich Theorem -- 4. Centrally Symmetric Polytopes -- 5. Kneserโs Conjecture -- 6. Sphere Coverings -- References -- X. Recent Results in the Theory of Packing and Covering -- 1. Introduction -- 2. Preliminaries and Basic Concepts -- 3. A Review of Some Classical Results in the Plane -- 4. Economical Packing in and Covering of the Plane -- 5. Multiple Packing and Covering -- 6. Some Computational Aspects of Packing and Covering -- 7. Restrictions on the Number of Neighbors in a Packing -- 8. Selected Topics in 3 Dimensions -- References -- XI. Recent Developments in Combinatorial Geometry -- 1. The Distribution of Distances -- 2. Graph Dimensions -- 3. Geometric Graphs -- 4. Arrangements of Lines in Space -- References -- XII. Set Theoretic Constructions in Euclidean Spaces -- 0. Introduction -- 1. Simple Transfinite Constructions -- 2. Closed Sets or Better Well-Orderings -- 3. Extending the Coloring More Carefully -- 4. The Use of the Continuum Hypothesis -- 5. The Infinite Dimensional Case -- 6. Large Paradoxical Sets in Another Sense -- References -- Author Index