The design and analysis of geometric algorithms has seen remarkable growth in recent years, due to their application in computer vision, graphics, medical imaging, and CAD. Geometric algorithms are built on three pillars: geometric data structures, algorithmic data structuring techniques and results from combinatorial geometry. This comprehensive presents a coherent and systematic treatment of the foundations and gives simple, practical algorithmic solutions to problems. An accessible approach to the subject, Algorithmic Geometry is an ideal guide for instructors or for beginning graduate courses in computational geometry.
In Collection
#57
Read It:
Yes
#57
Read It:
Yes
|
|
||||||||||||||||
Notes
Table of Contents
Preface xv
Translator's preface xix
Acknowledgments xxi
Part I — Algorithmic tools 1
Chapter 1 - Notions of complexity 3
1.1 The complexity of algorithms 3
1.1.1 The model of computation 3
1.1.2 Notions of complexity 4
1.1.3 Asymptotic behavior, notation 7
1.2 Optimality, lower bounds 9
1.2.1 The complexity of a problem 9
1.2.2 The example of sorting: decision trees 10
1.2.3 Lower bounds by transforming one problem into another ... 11
1.3 Bibliographical notes 12
Chapter 2 - Basic data structures 13
2.1 Terminology and features of the basic data structures 14
2.1.1 Lists, heaps, and queues 14
2.1.2 Dictionaries and priority queues 15
2.2 Balanced search trees 16
2.2.1 Graphs, trees, balanced trees 16
2.2.2 Red-black trees 17
2.3 Dictionary on a finite universe 25
2.4 Exercises 26
2.5 Bibliographical notes 30
Chapter 3 - Deterministic methods used in geometry 32
3.1 The divide-and-conquer method 33
3.1.1 Overview 33
3.1.2 An example: sorting n numbers using merge-sort 35
3.2 The sweep method 36
3.2.1 Overview 36
3.2.2 An example: computing the intersections of line segments 37
3.3 Vertical decompositions 40
3.3.1 Vertical decompositions of line segments 40
3.3.2 Vertical decompositions and simplified decompositions 42
3.4 Exercises 43
3.5 Bibliographical notes 44
Chapter 4 - Random sampling 46
4.1 Definitions 46
4.1.1 Objects, regions, and conflicts 46
4.1.2 Random sampling 49
4.2 Probabilistic theorems 50
4.2.1 The sampling theorem 51
4.2.2 The moment theorem 55
4.3 Exercises 57
4.4 Bibliographical notes 62
Chapter 5 - Randomized algorithms 63
5.1 The randomized incremental method 64
5.2 Off-line algorithms 65
5.2.1 The conflict graph 65
5.2.2 An example: vertical decomposition of line segments 69
5.3 On-line algorithms 75
5.3.1 The influence graph 75
5.3.2 An example: vertical decomposition of line segments 81
5.4 Accelerated incremental algorithms 84
5.4.1 The general method 84
5.4.2 An example: vertical decomposition of a polygon 87
5.5 Exercises 88
5.6 Bibliographical notes 92
Chapter 6 - Dynamic randomized algorithms 95
6.1 The probabilistic model 96
6.2 The augmented influence graph 97
6.3 Randomized analysis of dynamic algorithms 101
6.4 Dynamic decomposition of a set of line segments 110
6.5 Exercises 121
6.6 Bibliographical notes 123
Part II - Convex hulls 125
Chapter 7 - Polytopes 127
7.1 Definitions 127
7.1.1 Convex hulls, polytopes 127
7.1.2 Faces of a polytope 128
7.1.3 Polarity, dual of a polytope 135
7.1.4 Simple and simplicial polytopes 140
7.2 The combinatorics of polytopes 141
7.2.1 Euler's relation 141
7.2.2 The Dehn-Sommerville relations 144
7.2.3 The upper bound theorem 145
7.2.4 Cyclic polytopes 147
7.3 Projective polytopes, unbounded polytopes 148
7.3.1 Projective spaces 148
7.3.2 Oriented projective spaces 153
7.3.3 Projective polytopes, unbounded polytopes 156
7.4 Exercises 162
7.5 Bibliographical notes 168
Chapter 8 — Incremental convex hulls 169
8.1 Representation of polytopes 170
8.2 Lower bounds 171
8.3 Geometric preliminaries 171
8.4 A deterministic algorithm 176
8.5 On-line convex hulls 180
8.6 Dynamic convex hulls 186
8.7 Exercises 195
8.8 Bibliographical notes 197
Chapter 9 — Convex hulls in two and three dimensions 198
9.1 Representation of 2- and 3-polytopes 199
9.2 Divide-and-conquer convex hulls in dimension 2 201
9.3 Divide-and-conquer convex hulls in dimension 3 205
9.4 Convex hull of a polygonal line 214
9.5 Exercises 219
9.6 Bibliographical notes 221
Chapter 10 - Linear programming 223
10.1 Definitions 224
10.2 Randomized linear programming 225
10.3 Convex hulls using a shelling 227
10.4 Exercises 236
10.5 Bibliographical notes 239
Part III - Triangulations 241
Chapter 11 - Complexes and triangulations 243
11.1 Definitions 243
11.1.1 Simplices, complexes 243
11.1.2 Topological balls and spheres, singularities 245
11.1.3 Triangulations 247
11.1.4 Polygons and polyhedra 248
11.2 Combinatorics of triangulations 250
11.2.1 Euler's relation for topological balls and spheres 250
11.2.2 The complexity of 2-complexes 251
11.2.3 The complexity of 3-triangulations 255
11.3 Representation of complexes, duality 258
11.4 Exercises 260
11.5 Bibliographical notes 262
Chapter 12 - Triangulations in dimension 2 263
12.1 Triangulation of a set of points 264
12.1.1 The complexity of computing a triangulation 264
12.1.2 An incremental algorithm 264
12.2 Constrained triangulations 266
12.3 Vertical decompositions and triangulations of a polygon 267
12.3.1 Lower bound 267
12.3.2 Triangulating monotone polygons 269
12.3.3 Vertical decomposition and triangulation of a polygon 274
12.4 Exercises 281
12.5 Bibliographical notes 287
Chapter 13 - Triangulations in dimension 3 289
13.1 Triangulation of a set of points 290
13.1.1 The size of a triangulation 290
13.1.2 The split theorem 293
13.1.3 An incremental algorithm 296
13.2 Constrained triangulations 300
13.3 Vertical and simplicial decompositions 302
13.3.1 Vertical decomposition of a polyhedral region 302
13.3.2 Simplicial decomposition of a polyhedron of genus 0 307
13.4 Exercises 317
13.5 Bibliographical notes 318
Part IV — Arrangements 319
Chapter 14 - Arrangements of hyperplanes 321
14.1 Definitions 321
14.2 Combinatorial properties 322
14.3 The zone theorem 325
14.4 Incremental construction of an arrangement 330
14.4.1 The case of dimension 2 330
14.4.2 The case of dimensions higher than 2 331
14.5 Levels in hyperplane arrangements 333
14.5.1 Definitions 333
14.5.2 Combinatorial properties of levels 335
14.5.3 Computing the first k levels in an arrangement 335
14.6 Exercises 343
14.7 Bibliographical notes 350
Chapter 15 - Arrangements of line segments in the plane 352
15.1 Faces in an arrangement 353
15.2 Davenport-Schinzel sequences 353
15.3 The lower envelope of a set of functions 355
15.3.1 Complexity 356
15.3.2 Computing the lower envelope 358
15.4 A cell in an arrangement of line segments 358
15.4.1 Complexity 359
15.4.2 Computing a cell 362
15.5 Exercises 368
15.6 Bibliographical notes 371
Chapter 16 - Arrangements of triangles 373
16.1 Faces in an arrangement 374
16.2 Decomposing an arrangement of triangles 374
16.2.1 Vertical decomposition 375
16.2.2 Convex decomposition 377
16.3 The lower envelope of a set of triangles 379
16.3.1 Complexity 381
16.3.2 Vertical decomposition 383
16.3.3 Computing the lower envelope 384
16.4 A cell in an arrangement of triangles 390
16.4.1 Complexity 390
16.4.2 Vertical decomposition 394
16.4.3 Computing a cell 400
16.5 Exercises 402
16.6 Bibliographical notes 404
Part V — Voronoi diagrams 405
Chapter 17 - Euclidean metric 407
17.1 Definition 407
17.2 Voronoi diagrams and polytopes 408
17.2.1 Power of a point with respect to a sphere 408
17.2.2 Representation of spheres 409
17.2.3 The paraboloid V 410
17.2.4 Polarity 411
17.2.5 Orthogonal spheres 412
17.2.6 Radical hyperplane 414
17.2.7 Voronoi diagrams 414
17.3 Delaunay complexes 416
17.3.1 Definition and connection with Voronoi diagrams 416
17.3.2 Delaunay triangulations 418
17.3.3 Characteristic properties 418
17.3.4 Optimality of Delaunay triangulations 421
17.4 Higher-order Voronoi diagrams 425
17.5 Exercises 428
17.6 Bibliographical notes 431
Chapter 18 - Non-Euclidean metrics 433
18.1 Power diagrams 434
18.1.1 Definition and computation 434
18.1.2 Higher-order power diagrams 436
18.2 Affine diagrams 437
18.2.1 Affine diagrams and power diagrams 437
18.2.2 Diagrams for a general quadratic distance 438
18.3 Weighted diagrams 439
18.3.1 Weighted diagrams with additive weights 439
18.3.2 Weighted diagrams with multiplicative weights 442
18.4 L\ and L^ metrics 445
18.5 Voronoi diagrams in hyperbolic spaces 449
18.5.1 Pencils of spheres 449
18.5.2 Voronoi diagrams in hyperbolic spaces 450
18.6 Exercises 454
18.7 Bibliographical notes 457
Chapter 19 — Diagrams in the plane 459
19.1 A sweep algorithm 459
19.2 Voronoi diagram of a set of line segments 464
19.2.1 Definition and basic properties 464
19.2.2 A sweep algorithm 470
19.2.3 An incremental algorithm 471
19.2.4 The case of connected segments 476
19.2.5 Application to the motion planning of a disk 479
19.3 The case of points distributed in two planes 481
19.3.1 The two planes are parallel 481
19.3.2 The two planes are not parallel 485
19.4 Exercises 488
19.5 Bibliographical notes 490
References 492
Preface xv
Translator's preface xix
Acknowledgments xxi
Part I — Algorithmic tools 1
Chapter 1 - Notions of complexity 3
1.1 The complexity of algorithms 3
1.1.1 The model of computation 3
1.1.2 Notions of complexity 4
1.1.3 Asymptotic behavior, notation 7
1.2 Optimality, lower bounds 9
1.2.1 The complexity of a problem 9
1.2.2 The example of sorting: decision trees 10
1.2.3 Lower bounds by transforming one problem into another ... 11
1.3 Bibliographical notes 12
Chapter 2 - Basic data structures 13
2.1 Terminology and features of the basic data structures 14
2.1.1 Lists, heaps, and queues 14
2.1.2 Dictionaries and priority queues 15
2.2 Balanced search trees 16
2.2.1 Graphs, trees, balanced trees 16
2.2.2 Red-black trees 17
2.3 Dictionary on a finite universe 25
2.4 Exercises 26
2.5 Bibliographical notes 30
Chapter 3 - Deterministic methods used in geometry 32
3.1 The divide-and-conquer method 33
3.1.1 Overview 33
3.1.2 An example: sorting n numbers using merge-sort 35
3.2 The sweep method 36
3.2.1 Overview 36
3.2.2 An example: computing the intersections of line segments 37
3.3 Vertical decompositions 40
3.3.1 Vertical decompositions of line segments 40
3.3.2 Vertical decompositions and simplified decompositions 42
3.4 Exercises 43
3.5 Bibliographical notes 44
Chapter 4 - Random sampling 46
4.1 Definitions 46
4.1.1 Objects, regions, and conflicts 46
4.1.2 Random sampling 49
4.2 Probabilistic theorems 50
4.2.1 The sampling theorem 51
4.2.2 The moment theorem 55
4.3 Exercises 57
4.4 Bibliographical notes 62
Chapter 5 - Randomized algorithms 63
5.1 The randomized incremental method 64
5.2 Off-line algorithms 65
5.2.1 The conflict graph 65
5.2.2 An example: vertical decomposition of line segments 69
5.3 On-line algorithms 75
5.3.1 The influence graph 75
5.3.2 An example: vertical decomposition of line segments 81
5.4 Accelerated incremental algorithms 84
5.4.1 The general method 84
5.4.2 An example: vertical decomposition of a polygon 87
5.5 Exercises 88
5.6 Bibliographical notes 92
Chapter 6 - Dynamic randomized algorithms 95
6.1 The probabilistic model 96
6.2 The augmented influence graph 97
6.3 Randomized analysis of dynamic algorithms 101
6.4 Dynamic decomposition of a set of line segments 110
6.5 Exercises 121
6.6 Bibliographical notes 123
Part II - Convex hulls 125
Chapter 7 - Polytopes 127
7.1 Definitions 127
7.1.1 Convex hulls, polytopes 127
7.1.2 Faces of a polytope 128
7.1.3 Polarity, dual of a polytope 135
7.1.4 Simple and simplicial polytopes 140
7.2 The combinatorics of polytopes 141
7.2.1 Euler's relation 141
7.2.2 The Dehn-Sommerville relations 144
7.2.3 The upper bound theorem 145
7.2.4 Cyclic polytopes 147
7.3 Projective polytopes, unbounded polytopes 148
7.3.1 Projective spaces 148
7.3.2 Oriented projective spaces 153
7.3.3 Projective polytopes, unbounded polytopes 156
7.4 Exercises 162
7.5 Bibliographical notes 168
Chapter 8 — Incremental convex hulls 169
8.1 Representation of polytopes 170
8.2 Lower bounds 171
8.3 Geometric preliminaries 171
8.4 A deterministic algorithm 176
8.5 On-line convex hulls 180
8.6 Dynamic convex hulls 186
8.7 Exercises 195
8.8 Bibliographical notes 197
Chapter 9 — Convex hulls in two and three dimensions 198
9.1 Representation of 2- and 3-polytopes 199
9.2 Divide-and-conquer convex hulls in dimension 2 201
9.3 Divide-and-conquer convex hulls in dimension 3 205
9.4 Convex hull of a polygonal line 214
9.5 Exercises 219
9.6 Bibliographical notes 221
Chapter 10 - Linear programming 223
10.1 Definitions 224
10.2 Randomized linear programming 225
10.3 Convex hulls using a shelling 227
10.4 Exercises 236
10.5 Bibliographical notes 239
Part III - Triangulations 241
Chapter 11 - Complexes and triangulations 243
11.1 Definitions 243
11.1.1 Simplices, complexes 243
11.1.2 Topological balls and spheres, singularities 245
11.1.3 Triangulations 247
11.1.4 Polygons and polyhedra 248
11.2 Combinatorics of triangulations 250
11.2.1 Euler's relation for topological balls and spheres 250
11.2.2 The complexity of 2-complexes 251
11.2.3 The complexity of 3-triangulations 255
11.3 Representation of complexes, duality 258
11.4 Exercises 260
11.5 Bibliographical notes 262
Chapter 12 - Triangulations in dimension 2 263
12.1 Triangulation of a set of points 264
12.1.1 The complexity of computing a triangulation 264
12.1.2 An incremental algorithm 264
12.2 Constrained triangulations 266
12.3 Vertical decompositions and triangulations of a polygon 267
12.3.1 Lower bound 267
12.3.2 Triangulating monotone polygons 269
12.3.3 Vertical decomposition and triangulation of a polygon 274
12.4 Exercises 281
12.5 Bibliographical notes 287
Chapter 13 - Triangulations in dimension 3 289
13.1 Triangulation of a set of points 290
13.1.1 The size of a triangulation 290
13.1.2 The split theorem 293
13.1.3 An incremental algorithm 296
13.2 Constrained triangulations 300
13.3 Vertical and simplicial decompositions 302
13.3.1 Vertical decomposition of a polyhedral region 302
13.3.2 Simplicial decomposition of a polyhedron of genus 0 307
13.4 Exercises 317
13.5 Bibliographical notes 318
Part IV — Arrangements 319
Chapter 14 - Arrangements of hyperplanes 321
14.1 Definitions 321
14.2 Combinatorial properties 322
14.3 The zone theorem 325
14.4 Incremental construction of an arrangement 330
14.4.1 The case of dimension 2 330
14.4.2 The case of dimensions higher than 2 331
14.5 Levels in hyperplane arrangements 333
14.5.1 Definitions 333
14.5.2 Combinatorial properties of levels 335
14.5.3 Computing the first k levels in an arrangement 335
14.6 Exercises 343
14.7 Bibliographical notes 350
Chapter 15 - Arrangements of line segments in the plane 352
15.1 Faces in an arrangement 353
15.2 Davenport-Schinzel sequences 353
15.3 The lower envelope of a set of functions 355
15.3.1 Complexity 356
15.3.2 Computing the lower envelope 358
15.4 A cell in an arrangement of line segments 358
15.4.1 Complexity 359
15.4.2 Computing a cell 362
15.5 Exercises 368
15.6 Bibliographical notes 371
Chapter 16 - Arrangements of triangles 373
16.1 Faces in an arrangement 374
16.2 Decomposing an arrangement of triangles 374
16.2.1 Vertical decomposition 375
16.2.2 Convex decomposition 377
16.3 The lower envelope of a set of triangles 379
16.3.1 Complexity 381
16.3.2 Vertical decomposition 383
16.3.3 Computing the lower envelope 384
16.4 A cell in an arrangement of triangles 390
16.4.1 Complexity 390
16.4.2 Vertical decomposition 394
16.4.3 Computing a cell 400
16.5 Exercises 402
16.6 Bibliographical notes 404
Part V — Voronoi diagrams 405
Chapter 17 - Euclidean metric 407
17.1 Definition 407
17.2 Voronoi diagrams and polytopes 408
17.2.1 Power of a point with respect to a sphere 408
17.2.2 Representation of spheres 409
17.2.3 The paraboloid V 410
17.2.4 Polarity 411
17.2.5 Orthogonal spheres 412
17.2.6 Radical hyperplane 414
17.2.7 Voronoi diagrams 414
17.3 Delaunay complexes 416
17.3.1 Definition and connection with Voronoi diagrams 416
17.3.2 Delaunay triangulations 418
17.3.3 Characteristic properties 418
17.3.4 Optimality of Delaunay triangulations 421
17.4 Higher-order Voronoi diagrams 425
17.5 Exercises 428
17.6 Bibliographical notes 431
Chapter 18 - Non-Euclidean metrics 433
18.1 Power diagrams 434
18.1.1 Definition and computation 434
18.1.2 Higher-order power diagrams 436
18.2 Affine diagrams 437
18.2.1 Affine diagrams and power diagrams 437
18.2.2 Diagrams for a general quadratic distance 438
18.3 Weighted diagrams 439
18.3.1 Weighted diagrams with additive weights 439
18.3.2 Weighted diagrams with multiplicative weights 442
18.4 L\ and L^ metrics 445
18.5 Voronoi diagrams in hyperbolic spaces 449
18.5.1 Pencils of spheres 449
18.5.2 Voronoi diagrams in hyperbolic spaces 450
18.6 Exercises 454
18.7 Bibliographical notes 457
Chapter 19 — Diagrams in the plane 459
19.1 A sweep algorithm 459
19.2 Voronoi diagram of a set of line segments 464
19.2.1 Definition and basic properties 464
19.2.2 A sweep algorithm 470
19.2.3 An incremental algorithm 471
19.2.4 The case of connected segments 476
19.2.5 Application to the motion planning of a disk 479
19.3 The case of points distributed in two planes 481
19.3.1 The two planes are parallel 481
19.3.2 The two planes are not parallel 485
19.4 Exercises 488
19.5 Bibliographical notes 490
References 492