Contents Preface and Apology vii Chapter 1. Sylvester–Gallai Problem: The Beginnings of Combinatorial Geometry 1 1. James Joseph Sylvester and the Beginnings 1 2. Connecting Lines and Directions 3 3. Directions in Space vs. Points in the Plane 6 4. Proof of the Generalized Ungar Theorem 7 5. Colored Versions of the Sylvester–Gallai Theorem 10 Chapter 2. Arrangements of Surfaces: Evolution of the Basic Theory 13 1. Introduction 13 2. Preliminaries 16 3. Lower Envelopes 20 4. Single Cells 27 5. Zones 29 6. Levels 32 7. Many Cells and Related Problems 37 8. Generalized Voronoi Diagrams 40 9. Union of Geometric Objects 42 10. Decomposition of Arrangements 49 11. Representation of Arrangements 54 12. Computing Arrangements 56 13. Computing Substructures in Arrangements 58 14. Applications 63 15. Conclusions 70 Chapter 3. Davenport–Schinzel Sequences: The Inverse Ackermann Function in Geometry 73 1. Introduction 73 2. Davenport–Schinzel Sequences and Lower Envelopes 74 3. Simple Bounds and Variants 79 4. Sharp Upper Bounds on λs(n) 81 5. Lower Bounds on λs(n) 86 6. Davenport–Schinzel Sequences and Arrangements 89 Chapter 4. Incidences and Their Relatives: From Szemer´ edi and Trotter to Cutting Lenses 99 1. Introduction 99 2. Lower Bounds 102 v
Previous Page Next Page