Numerical methods in scientific computing

Cover......Page 1
Copyright......Page 3
Preface to Second Printing......Page 6
Preface......Page 8
Contents......Page 10
1.1 Historical Perspective......Page 14
1.1.1 Complexity notions in classical geometry......Page 15
1.1.2 The theory of convex sets, metric and combinatorial geometry......Page 17
1.1.3 Prior related work......Page 18
1.2 Algorithmic Background......Page 19
1.2.1 Algorithms: Their expression and performance evaluation......Page 20
1.2.2 Some considerations on general algorithmic techniques......Page 23
1.2.3 Data structures......Page 24
1.2.3.1 The segment tree......Page 26
1.2.3.2 The doubly-connected-edge-list (DCEL)......Page 28
1.3.1 General definitions and notations......Page 30
1.3.2 Invariants under groups of linear transformations......Page 32
1.3.3 Geometry duality. Polarity......Page 37
1.4 Models of Computation......Page 39
2.1 Introduction to Geometric Searching......Page 49
2.2.1 General considerations. Simple cases......Page 54
2.2.2.1 The slab method......Page 58
2.2.2.2 The chain method......Page 61
2.2.2.3 Optimal techniques: the planar-separator method, the triangulation refinement method, and the bridged chain method......Page 69
2.2.2.4 The trapezoid method......Page 76
2.3.1 General considerations......Page 83
2.3.2 The method of the multidimensional binary tree (k-D tree)......Page 87
2.3.3 A direct access method and its variants......Page 92
2.3.4 The range-tree method and its variants......Page 96
2.4 Iterated Search and Fractional Cascading......Page 101
2.5 Notes and Comments......Page 105
2.6 Exercises......Page 107
CHAPTER 3  Convex Hulls: Basic Algorithms......Page 108
3.1 Preliminaries......Page 109
3.2 Problem Statement and Lower Bounds......Page 112
3.3.1 Early development of a convex hull algorithm......Page 117
3.3.2 Graham\'s scan......Page 119
3.3.3 Jarvis\'s march......Page 123
3.3.4 QUICKHULL techniques......Page 125
3.3.5 Divide-and-conquer algorithms......Page 127
3.3.6 Dynamic convex hull algorithms......Page 130
3.3.7 A generalization: dynamic convex hull maintenance......Page 137
3.4.1 The gift-wrapping method......Page 144
3.4.2 The beneath-beyond method......Page 150
3.4.3 Convex hulls in three dimensions......Page 154
3.5 Notes and Comments......Page 159
3.6 Exercises......Page 161
4.1.1 Average-case analysis......Page 163
4.1.2 Approximation algorithms for convex hull......Page 167
4.1.3 The problem of the maxima of a point set......Page 170
4.1.4 Convex hull of a simple polygon......Page 179
4.2.1 Robust estimation......Page 184
4.2.2 Isotonic regression......Page 187
4.2.3 Clustering (diameter of a point set)......Page 189
4.3 Notes and Comments......Page 195
4.4 Exercises......Page 196
CHAPTER 5  Proximity: Fundamental Algorithms......Page 198
5.1 A Collection of Problems......Page 199
5.2 A Computational Prototype: Element Uniqueness......Page 204
5.3 Lower Bounds......Page 205
5.4 The Closest Pair Problem: A Divide-and-Conquer Approach......Page 208
5.5 The Locus Approach to Proximity Problems: The Voronoi Diagram......Page 217
5.5.1 A catalog of Voronoi properties......Page 218
5.5.2 Constructing the Voronoi diagram......Page 224
5.5.2.1 Constructing the dividing chain......Page 229
5.6 Proximity Problems Solved by the Voronoi Diagram......Page 233
5.7 Notes and Comments......Page 235
5.8 Exercises......Page 236
6.1 Euclidean Minimun1 Spanning Trees......Page 239
6.1.1 Euclidean traveling salesman......Page 243
6.2 Planar Triangulations......Page 247
6.2.1 The greedy triangulation......Page 248
6.2.2 Constrained triangulations......Page 250
6.2.2.1 Triangulating a monotone polygon......Page 252
6.3 Generalizations of the Voronoi Diagram......Page 254
6.3.1. Higher-order Voronoi diagrams (in the plane)......Page 255
6.3.1.1 Elements of inversive geometry......Page 256
6.3.1.2 The structure of higher-order Voronoi diagrams......Page 257
6.3.1.3 Construction of the higher-order Voronoi diagrams......Page 262
6.3.2 Multidimensional closest-point and farthest-point Voronoi diagrams......Page 266
6.4 Gaps and Covers......Page 268
6.5 Notes and Comments......Page 275
6.6 Exercises......Page 277
CHAPTER 7  Intersections......Page 279
7.1.1 The hidden-line and hidden-surface problems......Page 280
7.1.2 Pattern recognition......Page 281
7.1.3 Wire and component layout......Page 282
7.1.4 Linear programming and common intersection of half-spaces......Page 283
7.2.1 Intersection of convex polygons......Page 284
7.2.2 Intersection of star-shaped polygons......Page 290
7.2.3.1 Applications......Page 291
7.2.3.2 Segment intersection algorithms......Page 292
7.2.4 Intersection of half-planes......Page 300
7.2.5 Two-variable linear programming......Page 303
7.2.6 Kernel of a plane polygon......Page 312
7.3.1 Intersection of convex polyhedra......Page 319
7.3.2 Intersection of half-spaces......Page 328
7.4 Notes and Comments......Page 333
7.5 Exercises......Page 335
8.1.1 Aids for VLSI design......Page 336
8.1.2 Concurrency controls in databases......Page 338
8.2 Domain of Validity of the Results......Page 341
8.3 General Considerations on Static-Mode Algorithms......Page 343
8.4 Measure and Perimeter of a Union of Rectangles......Page 345
8.5 The Contour of a Union of Rectangles......Page 353
8.6 The Closure of a Union of Rectangles......Page 361
8.7 The External Contour of a Union of Rectangles......Page 366
8.8.1 Intersections of rectangles......Page 372
8.8.2 The rectangle intersection problem revisited......Page 376
8.8.3 Enclosure of rectangles......Page 379
8.9 Notes and Comments......Page 385
8.10 Exercises......Page 386
References......Page 387
Author Index......Page 398
Subject Index......Page 403