Polyhedral and Algebraic Methods in Computational Geometry

Cover......Page 1
Polyhedral and Algebraic Methods in Computational Geometry......Page 4
Audience and Required Background......Page 6
History and Acknowledgments......Page 7
Contents......Page 8
2.1 Projective Spaces......Page 12
2.2 Projective Transformations......Page 15
2.3 Convexity......Page 16
2.3.1 Orientation of Affine Hyperplanes......Page 17
2.3.2 Separation Theorems......Page 18
2.4 Exercises......Page 19
2.5 Remarks......Page 20
3.1 Definitions and Fundamental Properties......Page 21
3.1.1 The Faces of a Polytope......Page 22
3.1.2 First Consequences of the Separating Hyperplane Theorem......Page 24
3.1.3 The Outer Description of a Polytope......Page 25
3.2 The Face Lattice of a Polytope......Page 27
3.3 Polarity and Duality......Page 30
3.4 Polyhedra......Page 33
3.5 The Combinatorics of Polytopes......Page 36
3.6.1 Cyclic Polytopes......Page 42
3.6.3 Projective Transformations......Page 44
3.7 Exercises......Page 46
3.8 Remarks......Page 47
4.1 The Task......Page 49
4.2 Duality......Page 51
4.3 The Simplex Algorithm......Page 55
4.4 Determining a Start Vertex......Page 62
4.5 Inspection Using polymake......Page 63
4.6 Exercises......Page 65
4.7 Remarks......Page 66
5.1 Preliminary Considerations......Page 67
5.2 The Double Description Method......Page 68
5.3 Convex Hulls in the Plane......Page 74
5.4 Inspection Using polymake......Page 78
5.5 Exercises......Page 79
5.6 Remarks......Page 80
6.1 Voronoi Regions......Page 82
6.2 Polyhedral Complexes......Page 84
6.3 Voronoi Diagrams and Convex Hulls......Page 85
6.4 The Beach Line Algorithm......Page 89
Data Structures......Page 91
6.4.1 The Algorithm......Page 94
6.5 Determining the Nearest Neighbor......Page 97
6.6 Exercises......Page 98
6.7 Remarks......Page 99
7.1 Duality of Voronoi Diagrams......Page 100
7.2 The Delone Subdivision......Page 103
7.3 Computation of Volumes......Page 105
7.4 Optimality of Delone Triangulations......Page 106
7.5 Planar Delone Triangulations......Page 110
7.6 Inspection Using polymake......Page 115
7.8 Remarks......Page 117
8.1 Motivation......Page 118
8.2 Univariate Polynomials......Page 121
8.3 Resultants......Page 122
8.4 Plane Affine Algebraic Curves......Page 124
8.5 Projective Curves......Page 126
8.6 Bézout\'s Theorem......Page 128
8.7 Algebraic Curves Using Maple......Page 132
8.8 Exercises......Page 134
8.9 Remarks......Page 135
9.1 Ideals and the Univariate Case......Page 136
9.2 Monomial Orders......Page 140
9.3 Gröbner Bases and the Hilbert Basis Theorem......Page 144
9.4 Buchberger\'s Algorithm......Page 148
9.5 Binomial Ideals......Page 151
9.6 Proving a Simple Geometric Fact Using Gröbner Bases......Page 152
9.8 Remarks......Page 154
10.1 Gröbner Bases Using Maple and Singular......Page 156
10.2 Elimination of Unknowns......Page 157
10.3 Continuation of Partial Solutions......Page 161
10.4 The Nullstellensatz......Page 163
10.5 Solving Systems of Polynomial Equations......Page 166
10.6 Gröbner Bases and Integer Linear Programs......Page 170
10.8 Remarks......Page 176
11.1 Preliminary Considerations......Page 177
11.2 Medial Axis and Local Feature Size......Page 178
11.3 Samples and Polygonal Reconstruction......Page 181
11.4 The Algorithm NN-Crust......Page 183
11.6 Exercises......Page 186
11.7 Remarks......Page 188
12.1 Plücker Coordinates......Page 189
12.2 Exterior Multiplication and Exterior Algebra......Page 190
12.3 Duality......Page 195
12.4 Computations with Plücker Coordinates......Page 199
12.5 Lines in R3......Page 200
12.5.1 Transversals......Page 201
12.7 Remarks......Page 202
13.1 Voronoi Diagrams for Line Segments in the Plane......Page 204
13.2 Kinematic Problems and Motion Planning......Page 207
13.3 The Global Positioning System GPS......Page 214
13.4 Exercises......Page 216
13.5 Remarks......Page 217
A.1 Groups, Rings, Fields......Page 218
A.2 Polynomial Rings......Page 219
Appendix B: Separation Theorems......Page 221
C.1 Complexity of Algorithms......Page 224
C.2 The Complexity Classes P and NP......Page 226
The Complexity Class NP......Page 227
The Complexity Class #P......Page 228
Further Complexity Classes......Page 229
D.2 Maple......Page 230
D.5 Sage......Page 231
Appendix E: Notation......Page 233
References......Page 235
Index......Page 239