Algorithms in Combinatorial Geometry

Computational geometry as an area of research in its own right emerged in the early seventies of this century. Right from the beginning, it was obvious that strong connections of various kinds exist to questions studied in the considerably older field of combinatorial geometry. For example, the combinatorial structure of a geometric problem usually decides which algorithmic method solves the problem most efficiently. Furthermore, the analysis of an algorithm often requires a great deal of combinatorial knowledge. As it turns out, however, the connection between the two research areas commonly referred to as computa­ tional geometry and combinatorial geometry is not as lop-sided as it appears. Indeed, the interest in computational issues in geometry gives a new and con­ structive direction to the combinatorial study of geometry. It is the intention of this book to demonstrate that computational and com­ binatorial investigations in geometry are doomed to profit from each other. To reach this goal, I designed this book to consist of three parts, acorn binatorial part, a computational part, and one that presents applications of the results of the first two parts. The choice of the topics covered in this book was guided by my attempt to describe the most fundamental algorithms in computational geometry that have an interesting combinatorial structure. In this early stage geometric transforms played an important role as they reveal connections between seemingly unrelated problems and thus help to structure the field.

I Combinatorial Geometry.- 1 Fundamental Concepts in Combinatorial Geometry.- 1.1. Arrangements of Hyperplanes.- 1.2. Counting Faces and Incidences.- 1.3. Combinatorial Equivalence.- 1.4. Configurations of Points.- 1.5. Sylvester’s Problem.- 1.6. Convex Polytopes and Convex Polyhedra.- 1.7. Zonotopes.- 1.8. Voronoi Diagrams.- 1.9. Exercises and Research Problems.- 1.10. Bibliographic Notes.- 2 Permutation Tables.- 2.1. Circular Sequences.- 2.2. Encoding Arrangements and Configurations.- 2.3. A Circularly Non-Realizable 5-Sequence.- 2.4. Arrangements of Pseudo-Lines.- 2.5. Some Combinatorial Problems in the Plane.- 2.6. Exercises and Research Problems.- 2.7. Bibliographic Notes.- 3 Semispaces of Configurations.- 3.1. Semispaces and Arrangements.- 3.2. k-Sets and Levels in Arrangements.- 3.3. A Lower Bound on the Number of Bisections in the Plane.- 3.4. Lower Bounds on the Number of k-Sets in the Plane.- 3.5. Extensions to Three and Higher Dimensions..- 3.6. Semispaces and Circular Sequences.- 3.7. An Upper Bound on the Number of k-Sets in the Plane.- 3.8. Exercises and Research Problems.- 3.9. Bibliographic Notes.- 4 Dissections of Point Sets.- 4.1. Centerpoints.- 4.2. Ham-Sandwich Cuts.- 4.3. Erasing Subdivisions in the Plane.- 4.4. Simultaneous Four-Section in Three Dimensions.- 4.5. Erasing Cell Complexes in Three Dimensions.- 4.6. Generalizations to Higher Dimensions.- 4.7. Exercises and Research Problems.- 4.8. Bibliographic Notes.- 5 Zones in Arrangements.- 5.1. Supported Cells, Zones, and Duality.- 5.2. Sweeping a Simple Arrangement.- 5.3. Tight Bounds in the Plane.- 5.4. Asymptotically Tight Bounds in d Dimensions.- 5.5. An Implication of the Result on Zones.- 5.6. Exercises and Research Problems.- 5.7. Bibliographic Notes.- 6 The Complexity of Families of Cells.- 6.1. Definitions and Preliminary Results.- 6.2. The Complexity of a Polytope.- 6.2.1. Cyclic Polytopes.- 6.2.2. Euler’s Relation.- 6.2.3. The Dehn-Sommerville Relations.- 6.2.4. An Asymptotic Version of the Upper Bound Theorem.- 6.3. The Complexity of a Few Cells in Two Dimensions.- 6.4. Lower Bounds for Moderately Many Cells.- 6.5. Lower Bounds for Many Cells.- 6.6. Upper Bounds for Many Cells.- 6.7. Exercises and Research Problems.- 6.8. Bibliographic Notes.- II Fundamental Geometric Algorithms.- 7 Constructing Arrangements.- 7.1. Representing an Arrangement in Storage.- 7.2. The Incremental Approach.- 7.3. Initiating the Construction.- 7.4. Geometric Preliminaries.- 7.5. Incrementing the Arrangement.- 7.6. The Analysis of the Algorithm.- 7.7. Exercises and Research Problems.- 7.8. Bibliographie Notes.- 8 Constructing Convex Hulls.- 8.1. Convex Hulls and Duality.- 8.2. The Incidence Graph of a Convex Polytope.- 8.3. Two Algorithms in Two Dimensions.- 8.3.1. The Beneath-Beyond Method.- 8.3.2. Using Divide-and-Conquer.- 8.4. The Beneath-Beyond Method in d Dimensions.- 8.4.1. Geometric Preliminaries.- 8.4.2. Towards the Incrementation of the Convex Hull.- 8.4.3. Pyramidal Updates.- 8.4.4. Non-Pyramidal Updates.- 8.4.5. The Analysis of the Algorithm.- 8.5. Divide-and-Conquer in Three Dimensions.- 8.5.1. Coping with Degenerate Cases.- 8.5.2. The Upgraded Incidence Graph.- 8.5.3. Geometric Preliminaries.- 8.5.4. Wrapping Two Convex Polytopes.- 8.5.5. The Analysis of the Algorithm.- 8.6. Exercises and Research Problems.- 8.7. Bibliographic Notes.- 9 Skeletons in Arrangements.- 9.1. Skeletons and Eulerian Tours.- 9.2. Towards the Construction of a Skeleton.- 9.3. Constructing a Skeleton in a Simple Arrangement.- 9.4. Simulating Simplicity.- 9.4.1. A Conceptual Perturbation.- 9.4.2. Simulating the Perturbation.- 9.4.3. Computing the Sign of a Determinant of Polynomials..- 9.5. Penetration Search and Extremal Queries.- 9.5.1. Extremal Queries in the Plane.- 9.5.2. Extremal Queries in Three Dimensions: the Data Structure.- 9.5.3. Extremal Queries in Three Dimensions: the Query Algorithm.- 9.5.4. Dynamic Extremal Search.- 9.6. Exercises and Research Problems.- 9.7. Bibliographic Notes.- 10 Linear Programming..- 10.1. The Solution to a Linear Program.- 10.2. Linear Programming and Duality.- 10.3. Linear Programming in Two Dimensions.- 10.3.1. Prune: Eliminate Redundant Half-Planes.- 10.3.2. Bisect: Decrease the Range of the Linear Program.- 10.3.3. Find_Test: Determine the Median.- 10.3.4. Assembling the Algorithm.- 10.4. Linear Programming in Three and Higher Dimensions.- 10.4.1. The Geometry of Pruning.- 10.4.2. The Geometry of Bisecting.- 10.4.3. Searching Lines in the Plane.- 10.4.4. The Geometry of Searching.- 10.4.5. The Overall Algorithm.- 10.5. Exercises and Research Problems.- 10.6. Bibliographic Notes.- 11 Planar Point Location Search.- 11.1. Euler’s Relation for Planar Graphs.- 11.2. The Geometry of Monotone Subdivisions.- 11.3. A Tree of Separators for Point Location.- 11.4. Representing a Plane Subdivision.- 11.5. Constructing a Family of Separators.- 11.6. Optimal Search by Connecting Separators.- 11.7. Constructing the Layered DAG.- 11.8. Refining Non-Monotone Subdivisions.- 11.9. Exercises and Research Problems.- 11.10. Bibliographic Notes.- III Geometric and Algorithmic Applications.- 12 Problems for Configurations and Arrangements.- 12.1. Largest Convex Subsets.- 12.2. The Visibility Graph for Line Segments.- 12.3. Degeneracies in Configurations.- 12.4. Minimum Measure Simplices.- 12.5. Computing Ranks: Sorting in d Dimensions?.- 12.6. A Vector-Sum Maximization Problem.- 12.7. Exercises and Research Problems.- 12.8. Bibliographic Notes.- 13 Voronoi Diagrams.- 13.1. Classical Voronoi Diagrams.- 13.2. Applications in the Plane.- 13.2.1. The Post Office Problem.- 13.2.2. Triangulating Point Sets.- 13.2.3. Delaunay Triangulations from Convex Hulls.- 13.2.4. Finding Closest Neighbors.- 13.2.5. Minimum Spanning Trees.- 13.2.6. Shapes of Point Sets.- 13.3. Higher-Order Voronoi Diagrams.- 13.4. The Complexity of Higher-Order Voronoi Diagrams.- 13.5. Constructing Higher-Order Voronoi Diagrams.- 13.6. Power Diagrams.- 13.7. Exercises and Research Problems.- 13.8. Bibliographic Notes.- 14 Separation and Intersection in the Plane.- 14.1. Constructing Ham-Sandwich Cuts in Two Dimensions.- 14.1.1. Ham-Sandwich Cuts and Duality.- 14.1.2. Testing a Line.- 14.1.3. Finding Test Lines and Pruning.- 14.1.4. The Overall Algorithm.- 14.2. Answering Line Queries.- 14.2.1. The Ham-Sandwich Tree.- 14.2.2. Point Location in Arrangements.- 14.3. A Self-Dual Intersection Problem.- 14.4. Triangular Range Queries.- 14.5. Exercises and Research Problems.- 14.6. Bibliographic Notes.- 15 Paradigmatic Design of Algorithms.- 15.1. The Problem: Stabbing Line Segments in the Plane.- 15.2. Geometric Transformation.- 15.3. Combinatorial Analysis.- 15.4. Divide-and-Conquer.- 15.5. Incremental Construction.- 15.6. Prune-and-Search.- 15.7. The Locus Approach.- 15.8. Dynamization by Decomposition.- 15.9. Exercises and Research Problems.- 15.10. Bibliographic Notes.- References.- Appendix A Definitions.- Appendix B Notational Conventions.