Algorithms in Combinatorial Geometry

Cover......Page 1
Series......Page 2
Title page......Page 3
Date-line......Page 4
Dedication......Page 5
Preface......Page 7
TABLE OF CONTENTS......Page 11
PART I COMBINATORIAL GEOMETRY......Page 17
CHAPTER 1 Fundamental Concepts in Combinatorial Geometry......Page 19
1.1. Arrangements of Hyperplanes......Page 20
1.2. Counting Faces and Incidences......Page 22
1.3. Combinatorial Equivalence......Page 26
1.4. Configurations of Points......Page 28
1.5. Sylvester's Problem......Page 31
1.6. Convex Polytopes and Convex Polyhedra......Page 32
1.7. Zonotopes......Page 36
1.8. Voronoi Diagrams......Page 39
1.9. Exercises and Research Problems......Page 41
1.10. Bibliographic Notes......Page 43
2.1. Circular Sequences......Page 45
2.2. Encoding Arrangements and Configurations......Page 48
2.3. A Circularly Non-Realizable 5-Sequence......Page 51
2.4. Arrangements of Pseudo-Lines......Page 53
2.5. Some Combinatorial Problems in the Plane......Page 55
2.6. Exercises and Research Problems......Page 57
2.7. Bibliographic Notes......Page 60
CHAPTER 3 Semispaces of Configurations......Page 61
3.1. Semispaces and Arrangements......Page 62
3.2. $k$-Sets and Levels in Arrangements......Page 63
3.3. A Lower Bound on the Number of Bisections in the Plane......Page 66
3.4. Lower Bounds on the Number of $k$-Sets in the Plane......Page 68
3.5. Extensions to Three and Higher Dimensions......Page 70
3.6. Semispaces and Circular Sequences......Page 71
3.7. An Upper Bound on the Number of $k$-Sets in the Plane......Page 74
3.8. Exercises and Research Problems......Page 76
3.9. Bibliographic Notes......Page 77
4.1. Centerpoints......Page 79
4.2. Ham-Sandwich Cuts......Page 82
4.3. Erasing Subdivisions in the Plane......Page 86
4.4. Simultaneous Four-Section in Three Dimensions......Page 89
4.5. Erasing Cell Complexes in Three Dimensions......Page 93
4.6. Generalizations to Higher Dimensions......Page 94
4.7. Exercises and Research Problems......Page 95
4.8. Bibliographic Notes......Page 97
CHAPTER 5 Zones in Arrangements......Page 99
5.1. Supported Cells, Zones, and Duality......Page 100
5.2. Sweeping a Simple Arrangement......Page 102
5.3. Tight Bounds in the Plane......Page 105
5.4. Asymptotically Tight Bounds in $d$ Dimensions......Page 109
5.5. An Implication of the Result on Zones......Page 110
5.6. Exercises and Research Problems......Page 111
5.7. Bibliographic Notes......Page 112
CHAPTER 6 The Complexity of Families of Cells......Page 113
6.1. Definitions and Preliminary Results......Page 114
6.2. The Complexity of a Polytope......Page 115
6.2.1. Cyclic Polytopes......Page 116
6.2.2. Euler's Relation......Page 118
6.2.3. The Dehn-Sommerville Relations......Page 120
6.2.4. An Asymptotic Version of the Upper Bound Theorem......Page 122
6.3. The Complexity of a Few Cells in Two Dimensions......Page 123
6.4. Lower Bounds for Moderately Many Cells......Page 125
6.5. Lower Bounds for Many Cells......Page 127
6.6. Upper Bounds for Many Cells......Page 130
6.7. Exercises and Research Problems......Page 132
6.8. Bibliographic Notes......Page 134
PART II FUNDAMENTAL GEOMETRIC ALGORITHMS......Page 137
7.1. Representing an Arrangement in Storage......Page 139
7.2. The Incremental Approach......Page 141
7.3. Initiating the Construction......Page 142
7.4. Geometric Preliminaries......Page 144
7.5. Incrementing the Arrangement......Page 146
7.6. The Analysis of the Algorithm......Page 150
7.7. Exercises and Research Problems......Page 152
7.8. Bibliographic Notes......Page 153
CHAPTER 8 Constructing Convex Hulls......Page 155
8.1. Convex Hulls and Duality......Page 156
8.2. The Incidence Graph of a Convex Polytope......Page 157
8.3. Two Algorithms in Two Dimensions......Page 158
8.3.1. The Beneath-Beyond Method......Page 159
8.3.2. Using Divide-and-Conquer......Page 161
8.4. The Beneath-Beyond Method in $d$ Dimensions......Page 163
8.4.1. Geometric Preliminaries......Page 164
8.4.2. Towards the Incrementation of the Convex Hull......Page 168
8.4.3. Pyramidal Updates......Page 169
8.4.4. Non-Pyramidal Updates......Page 170
8.4.5. The Analysis of the Algorithm......Page 172
8.5. Divide-and-Conquer in Three Dimensions......Page 174
8.5.1. Coping with Degenerate Cases......Page 175
8.5.2. The Upgraded Incidence Graph......Page 176
8.5.3. Geometric Preliminaries......Page 178
8.5.4. Wrapping Two Convex Polytopes......Page 183
8.5.5. The Analysis of the Algorithm......Page 188
8.6. Exercises and Research Problems......Page 189
8.7. Bibliographic Notes......Page 191
CHAPTER 9 Skeletons in Arrangements......Page 193
9.1. Skeletons and Eulerian Tours......Page 194
9.2. Towards the Construction of a Skeleton......Page 197
9.3. Constructing a Skeleton in a Simple Arrangement......Page 199
9.4. Simulating Simplicity......Page 201
9.4.1. A Conceptual Perturbation......Page 202
9.4.2. Simulating the Perturbation......Page 204
9.4.3. Computing the Sign of a Determinant of Polynomials......Page 206
9.5. Penetration Search and Extremal Queries......Page 208
9.5.1. Extremal Queries in the Plane......Page 209
9.5.2. Extremal Queries in Three Dimensions: the Data Structure......Page 211
9.5.3. Extremal Queries in Three Dimensions: the Query Algorithm......Page 217
9.5.4. Dynamic Extremal Search......Page 218
9.6. Exercises and Research Problems......Page 221
9.7. Bibliographic Notes......Page 224
CHAPTER 10 Linear Programming......Page 225
10.1. The Solution to a Linear Program......Page 226
10.2. Linear Programming and Duality......Page 228
10.3. Linear Programming in Two Dimensions......Page 230
10.3.1. Prune: Eliminate Redundant Half-Planes......Page 231
10.3.2. Bisect: Decrease the Range of the Linear Program......Page 233
10.3.3. Find_Test: Determine the Median......Page 235
10.3.4. Assembling the Algorithm......Page 236
10.4. Linear Programming in Three and Higher Dimensions......Page 239
10.4.1. The Geometry of Pruning......Page 240
10.4.2. The Geometry of Bisecting......Page 241
10.4.3. Searching Lines in the Plane......Page 244
10.4.4. The Geometry of Searching......Page 246
10.4.5. The Overall Algorithm......Page 250
10.5. Exercises and Research Problems......Page 252
10.6. Bibliographic Notes......Page 254
CHAPTER 11 Planar Point Location Search......Page 257
11.1. Euler's Relation for Planar Graphs......Page 258
11.2. The Geometry of Monotone Subdivisions......Page 260
11.3. A Tree of Separators for Point Location......Page 264
11.4. Representing a Plane Subdivision......Page 267
11.5. Constructing a Family of Separators......Page 268
11.6. Optimal Search by Connecting Separators......Page 272
11.7. Constructing the Layered DAG......Page 274
11.8. Refining Non-Monotone Subdivisions'......Page 276
11.9. Exercises and Research Problems......Page 278
11.10. Bibliographic Notes......Page 281
PART III GEOMETRIC AND ALGORITHMIC APPLICATIONS......Page 285
CHAPTER 12 Problems for Configurations and Arrangements......Page 287
12.1. Largest Convex Subsets......Page 288
12.2. The Visibility Graph for Line Segments......Page 291
12.3. Degeneracies in Configurations......Page 294
12.4. Minimum Measure Simplices......Page 298
12.5. Computing Ranks: Sorting in $d$ Dimensions?......Page 300
12.6. A Vector-Sum Maximization Problem......Page 302
12.7. Exercises and Research Problems......Page 304
12.8. Bibliographic Notes......Page 306
CHAPTER 13 Voronoi Diagrams......Page 309
13.1. Classical Voronoi Diagrams......Page 310
13.2.1. The Post Office Problem......Page 314
13.2.2. Triangulating Point Sets......Page 315
13.2.3. Delaunay Triangulations from Convex Hulls......Page 319
13.2.5. Minimum Spanning Trees......Page 322
13.2.6. Shapes of Point Sets......Page 325
13.3. Higher-Order Voronoi Diagrams......Page 331
13.4. The Complexity of Higher-Order Voronoi Diagrams......Page 335
13.5. Constructing Higher-Order Voronoi Diagrams......Page 340
13.6. Power Diagrams......Page 343
13.7. Exercises and Research Problems......Page 344
13.8. Bibliographic Notes......Page 348
CHAPTER 14 Separation and Intersection in the Plane......Page 351
14.1.1. Ham-Sandwich Cuts and Duality......Page 352
14.1.2. Testing a Line......Page 355
14.1.3. Finding Test Lines and Pruning......Page 357
14.1.4. The Overall Algorithm......Page 359
14.2.1. The Ham-Sandwich Tree......Page 361
14.2.2. Point Location in Arrangements......Page 364
14.3. A Self-Dual Intersection Problem......Page 365
14.4. Triangular Range Queries......Page 367
14.5. Exercises and Research Problems......Page 370
14.6. Bibliographic Notes......Page 372
15.1. The Problem: Stabbing Line Segments in the Plane......Page 375
15.2. Geometric Transformation......Page 377
15.3. Combinatorial Analysis......Page 379
15.4. Divide-and-Conquer......Page 381
15.5. Incremental Construction......Page 383
15.6. Prune-and-Search......Page 386
15.7. The Locus Approach......Page 387
15.8. Dynamization by Decomposition......Page 389
15.9. Exercises and Research Problems......Page 392
15.10. Bibliographic Notes......Page 394
REFERENCES......Page 397
APPENDIX A Definitions......Page 411
APPENDIX B Notational Conventions......Page 425
INDEX......Page 433