El. knyga: New Trends in Discrete and Computational Geometry

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. Welzls Minidisk
Algorithm.-
9. Clarksons 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: VerticalL?-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-Levis 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-Levis Covering Problem
for Convex Polyhedra with Affine Symmetry.- References.- IX. Geometric and
Combinatorial Applications of Borsuks Theorem.-
1. Introduction.-
2. Van
Kampen-Flores Type Results.-
3. The Ham-Sandwich Theorem.-
4. Centrally
Symmetric Polytopes.-
5. Knesers 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.- AuthorIndex.