《算法設計技巧與分析（英文版）》是2013年電子工業出版社出版的圖書，作者是M. H. 阿蘇外耶。
基本介紹
- 中文名：算法設計技巧與分析（英文版）
- 作者：M. H. Alsuwaiyel（M. H. 阿蘇外耶）
- 譯者：M. H. Alsuwaiyel
- 出版社：電子工業出版社
- 出版時間：2013年
- ISBN：9787121204197
- 千 字 數：632
內容簡介,目錄,
內容簡介
本書涵蓋了絕大多數算法設計中的一般技術，在表達每一種技術時，闡述它的套用背景，注意用與其他技術比較的方法說明它的特徵，並提供大量相應實際問題的例子。全書分七部分19章，從算法設計和算法分析的基本概念和方法入手，先後介紹了遞歸技術、分治、動態規劃、貪心算法、圖的遍歷等技術，並且對NP完全問題進行了基本但清楚的討論。
目錄
PART 1 Basic Concepts and Introduction to Algorithms 1
Chapter 1 Basic Concepts in Algorithmic Analysis 5
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Historical Background . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Analysis of the binary search algorithm . . . . . . . . . 10
1.4 Merging Two Sorted Lists . . . . . . . . . . . . . . . . . . . . . 12
1.5 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 BottomJ.Jp Merge Sorting . . . . . . . . . . . . . . . . . . . . . 17
1.7.1 Analysis of bottom-up merge sorting . . . . . . . . . . . 19
1.8 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.8.1 Order of growth . . . . . . . . . . . . . . . . . . . . . . 21
1.8.2 The O-notation . . . . . . . . . . . . . . . . . . . . . . . 25
1.8.3 The Ω-notation . . . . . . . . . . . . . . . . . . . . . . . 26
1.8.4 The Θ-notation . . . . . . . . . . . . . . . . . . . . . . . 27
1.8.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.8.6 Complexity classes and the e notation . . . . . . . . . . 31
1.9 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.10 optimal Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 34
1.11 How to Estimate the Running Time of an Algorithm . . . . . .35
1.11.1 Counting the number of iterations . . . . . . . . . . . .35
1.11.2 Counting the frequency of basic operations. . .38
1.11.3 Using recurrence relations . . . . . . . . . . . . . . . . .41
1.12 Worst case and average case analysis . . . . . . . . . . . . . . 42
1.12.1 Worst case analysis . . . . . . . . . . . . . . . . . . . . .44
1.12.2 Average case analysis . . . . . . . . . . . . . . . . . . .46
1.13 Amortized Analysis . . . . . . . . . . . . . . . . . . . . . . . . .47
1.14 Input Size and Problem Instance . . . . . . . . . . . . . . . . .50
1.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52
1.16 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . .59
Chapter 2 Mathematical Preliminaries 61
2.1 Sets, Relations and Functions . . . . . . . . . . . . . . . . . . .62
2.1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62
2.1.2 Relations . . . . . . . . . . . . . . . . . . . . . . . . . .63
2.1.2.1 Equivalence relations . . . . . . . . . . . . . .64
2.1.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . .64
2.2 Proof Methods . . . . . . . . . . . . . . . . . . . . . . . . . . .65
2.2.1 Direct proof . . . . . . . . . . . . . . . . . . . . . . . . .65
2.2.2 Indirect proof . . . . . . . . . . . . . . . . . . . . . . . .66
2.2.3 Proof by contradiction . . . . . . . . . . . . . . . . . . .66
2.2.4 Proof by counterexampIe . . . . . . . . . . . . . . . . .67
2.2.5 Mathematic induction . . . . . . . . . . . . . . . . . .68
2.3 Logarithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . .69
2.4 Floor and Ceiling Functions . . . . . . . . . . . . . . . . . . . .70
2.5 Factorial and Binomial Coefficients . . . . . . . . . . . . . . . .71
2.5.1 Factorials . . . . . . . . . . . . . . . . . . . . . . . . . .71
2.5.2 Binomial coefficients . . . . . . . . . . . . . . . . . . 73
2.6 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . .75
2.7 summations. . . . . . . . . . . . . . . . . . . . . . . . . . . . .76
2.7.1 Approximation of summations by integration . . . . . .78
2.8 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . .82
2.8.1 Solution of linear homogeneous recurrences . . . . . . .83
2.8.2 Solution of inhomogeneous recurrences . . . . . . . . . .85
2.8.3 Solution of divide-and-conquer recurrences . . . . . .87
2.8.3.1 Expanding the recurrence . . . . . . . . . . .87
2.8.3.2 Substitution . . . . . . . . . . . . . . . . . . .91
2.8.3.3 Change of variables . . . . . . . . . . . . . . . 95
2.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Chapter 3 Data Structures 103
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.2 LinkedLists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.2.1 Stacks and queues . . . . . . . . . . . . . . . . . . . . . 104
3.3 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.3.1 Representation of graphs . . . . . . . . . . . . . . . . . 106
3.3.2 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . 107
3.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.5 RootedTYees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.5.1 Tree traversals . . . . . . . . . . . . . . . . . . . . . . . 109
3.6 Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.6.1 Some quantitative aspects of binary trees . . . . . . . . 111
3.6.2 Binary search trees . . . . . . . . . . . . . . . . . . . . . 112
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
3.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 114
Chapter 4 Heaps and the Disjoint Sets Data Structures 115
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.2 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.2.1 Operations on heaps . . . . . . . . . . . . . . . . . . . . 116
4.2.2 Creating a heap . . . . . . . . . . . . . . . . . . . . . . 120
4.2.3 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.2.4 Min and max heaps . . . . . . . . . . . . . . . . . . . . 125
4.3 Disjoint Sets Data Structures . . . . . . . . . . . . . . . . . . . 125
4.3.1 The union by rank heuristic . . . . . . . . . . . . . . . . 127
4.3.2 Path compression . . . . . . . . . . . . . . . . . . . . 129
4.3.3 The union-find algorithms . . . . . . . . . . . . . . . . . 130
4.3.4 Analysis of the union-find algorithms . . . . . . . . . . . 132
4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.5 Bibliographic Notes. . . . . . . . . . . . . . . . . . . . . . . . . 137
PART 2 Techniques Based on Recursion 139
Chapter 5 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . .143
5.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . .143
5.2 Two Simple Examples . . . . . . . . . . . . . . . . . . . . . . .144
5.2.1 Selection sort . . . . . . . . . . . . . . . . . . . . . . . .144
5.2.2 Insertion sort . . . . . . . . . . . . . . . . . . . . . . . .145
5.3 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . .145
5.4 Integer Exponentiation . . . . . . . . . . . . . . . . . . . . . . .148
5.5 Evaluating Polynomials (Horner’s Rule) . . . . . . . . . . . . .149
5.6 Generating Permutations . . . . . . . . . . . . . . . . . . . . .150
5.6.1 The first algorithm . . . . . . . . . . . . . . . . . . . . .150
5.6.2 The second algorithm . . . . . . . . . . . . . . . . . . .152
5.7 Finding the Majority Element . . . . . . . . . . . . . . . . . . .154
5.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . .158
5.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .158
Chapter 6 Divide and Conquer 161
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .161
6.2 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . .163
6.3 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165
6.3.1 How the algorithm Works . . . . . . . . . . . . . . . . .166
6.3.2 Analysis of the mergesort algorithm . . . . . . . . . . .167
6.4 Selection: Finding the Median and the kth Smallest Element .169
6.5 The Divide and Conquer Paradigm . . . . . . . . . . . . . . . .172
6.5.1 Analysis of the selection algorithm . . . . . . . . . . . .175
6.6 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .177
6.6.1 A partitioning algorithm . . . . . . . . . . . . . . . . . .177
6.6.2 The sorting Algorithm . . . . . . . . . . . . . . . . . . .179
6.6.3 Analysis of the quicksort algorithm . . . . . . . . . . . .181
6.6.3.1 The worst case behavior . . . . . . . . . . . .181
6.6.3.2 The average case behavior . . . . . . . . . . .184
6.6.4Comparison of sorting algorithms . . . . . . . . . . . . .186
6.7 Multiplication of Large Integers . . . . . . . . . . . . . . . . . .187
6.8 Matrix Multiplication. . . . . . . . . . . . . . . . . . . . . . .188
6.8.1 The traditional algorithm . . . . . . . . . . . . . . . . .188
6.8.2 Recursive version . . . . . . . . . . . . . . . . . . . . . .188
6.8.3 Strassen’s algorithm . . . . . . . . . . . . . . . . . . . .190
6.8.4 Comparisons of the three algorithms . . . . . . . . . . .191
6.9 The Closest Pair Problem . . . . . . . . . . . . . . . . . . . . .192
6.9.1 Time complexity . . . . . . . . . . . . . . . . . . . . . .194
6.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
6.11 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 202
Chapter 7 Dynamic Programming 203
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203
7.2 The Longest Common Subsequence Problem . . . . . . . . . .205
7.3 Matrix Chain Multiplication . . . . . . . . . . . . . . . . . . . .208
7.4 The Dynamic Programming Paradigm . . . . . . . . . . . . . .214
7.5 The All-Pairs Shortest Path Problem . . . . . . . . . . . . . . .215
7.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .217
7.6 The Knapsack Problem . . . . . . . . . . . . . . . . . . . . . .220
7.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . .226
PART 3 First-Cut Techniques 227
Chapter 8 The Greedy Approach 231
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
8.2 The Shortest Path Problem . . . . . . . . . . . . . . . . . . . . 232
8.2.1 A linear time algorithm for dense graphs . . . . . . . . 237
8.3 Minimum Cost Spanning Trees (Kruskal’s Algorithm) . . . . . 239
8.4 Minimum Cost Spanning Trees (Prim’s Algorithm) . . . . . . . 242
8.4.1 A linear time algorithm for dense graphs . . . . . . . . 246
8.5 File Compression . . . . . . . . . . . . . . . . . . . . . . . . . . 248
8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
8.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 255
Chapter 9 Graph Traversal 257
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
9.2 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . 257
9.2.1 Time complexity of depth-first search . . . . . . . . . . 261
9.3 Applications of Depth-First Search . . . . . . . . . . . . . . . . 262
9.3.1 Graph acyclicity. . . . . . . . . . . . . . . . . . . . . . 262
9.3.2 Topological sorting . . . . . . . . . . . . . . . . . . . . . 262
9.3.3 Finding articulation points in a graph . . . . . . . . . . 263
9.3.4 Strongly connected components . . . . . . . . . . . . . . 266
9.4 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . . . 267
9.5 Applications of Breadth-First Search . . . . . . . . . . . . . . . 269
9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
9.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 273
PART 4 Complexity of Problems 2 75
Chapter 10 NP-complete Problems 279
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
10.2 The Class P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
10.3 The Class NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
10.4 NP-complete Problems . . . . . . . . . . . . . . . . . . . . . . . 285
10.4.1 The satisfiability problem . . . . . . . . . . . . . . . . . 285
10.4.2 Vertex cover, independent set and clique problems . . . 288
10.4.3 More NP-complete Problems . . . . . . . . . . . . . . . 291
10.5 The Class co-NP . . . . . . . . . . . . . . . . . . . . . . . . . . 292
10.6 The Class NPI . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
10.7 The Relationships Between the Four Classes . . . . . . . . . . . 295
10.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
10.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 298
Chapter 11 Introduction to Computational Complexity 299
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
11.2 Model of Computation: The Turing Machine . . . . . . . . . . . 299
11.3 k-tape Turing Machines and Time complexity . . . . . . . . . . 300
11.4 Off-Line Turing Machines and Space Complexity . . . . . . . . 303
11.5 Tape Compression and Linear Speed-Up . . . . . . . . . . . . . 305
11.6 Relationships Between Complexity Classes . . . . . . . . . . . . 306
11.6.1 Space and time hierarchy theorems . . . . . . . . . . . . 309
11.6.2 Padding arguments . . . . . . . . . . . . . . . . . . . . . 311
11.7 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
11.8 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
11.8.1 NLOGSPACE-complete problems . . . . . . . . . . . . 318
11.8.2 PSPACE-complete problems . . . . . . . . . . . . . . . 319
11.8.3 P-complete problems . . . . . . . . . . . . . . . . . . . . 321
11.8.4 Some conclusions of completeness . . . . . . . . . . . . . 323
11.9 The Polynomial Time Hierarchy . . . . . . . . . . . . . . . . . 324
11.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
11.11 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 332
Chapter 12 Lower Bounds 335
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
12.2 Trivial Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . 335
12.3 The Decision Tree Model . . . . . . . . . . . . . . . . . . . . . 336
12.3.1 The search problem . . . . . . . . . . . . . . . . . . . . 336
12.3.2 The sorting problem . . . . . . . . . . . . . . . . . . . . 337
12.4 The Algebraic Decision Tree Model . . . . . . . . . . . . . . . . 339
12.4.1 The element uniqueness problem . . . . . . . . . . . . . 341
12.5 Linear Time Reductions . . . . . . . . . . . . . . . . . . . . . . 342
12.5.1 The convex hull problem . . . . . . . . . . . . . . . . . 342
12.5.2 The closest pair problem . . . . . . . . . . . . . . . . . 343
12.5.3 The Euclidean minimum spanning tree problem . . . . . 344
12.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
12.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 346
PART 5 Coping with Hardness 349
Chapter 13 Backtracking 353
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
13.2 The 3-Coloring Problem . . . . . . . . . . . . . . . . . . . . . . 353
13.3 The 8-Queens Problem . . . . . . . . . . . . . . . . . . . . . . . 357
13.4 The General Backtracking Method . . . . . . . . . . . . . . . . 360
13.5 Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . 362
13.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
13.7 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . 369
Chapter 14 Randomized Algorithms 371
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
14.2 Las Vegas and Monte Carlo Algorithms . . . . . . . . . . . . . 372
14.3 Randomized Quicksort . . . . . . . . . . . . . . . . . . . . . . . 373
14.4 Randomized Selection . . . . . . . . . . . . . . . . . . . . . . . 374
14.5 Testing String Equality . . . . . . . . . . . . . . . . . . . . . . 377
14.6 Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . . . . 379
14.7 Random Sampling . . . . . . . . . . . . . . . . . . . . . . . . . 381
14.8 Primality Testing . . . . . . . . . . . . . . . . . . . . . . . . . . 384
14.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
14.10Bibliographic Notes. . . . . . . . . . . . . . . . . . . . . . . . . 392
Chapter 15 Approximation Algorithms . . . . . . . . . . . . . . . . . . . 393
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
15.2 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 393
15.3 Difference Bounds . . . . . . . . . . . . . . . . . . . . . . . . . 394
15.3.1 Planar graph coloring . . . . . . . . . . . . . . . . . . . 395
15.3.2 Hardness result: the knapsack problem . . . . . . . . . 395
15.4 Relative Performance Bounds . . . . . . . . . . . . . . . . . . . 396
15.4.1 The bin packing problem . . . . . . . . . . . . . . . . . 397
15.4.2 The Euclidean traveling salesman problem . . . . . . . 399
15.4.3 The vertex cover problem . . . . . . . . . . . . . . . . . 401
15.4.4 Hardness result: the traveling salesman problem . . . . 402
15.5 Polynomial Approximation Schemes . . . . . . . . . . . . . . . 404
15.5.1 The knapsack problem . . . . . . . . . . . . . . . . . . . 404
15.6 Fully Polynomial Approximation Schemes . . . . . . . . . . . . 407
15.6.1 The subset-sum problem . . . . . . . . . . . . . . . . . . 408
15.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
15.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 413
PART 6 Iterative Improvement for Domain-Specific Problems 415
Chapter 16 Network Flow 419
16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
16.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
16.3 The Ford-Fulkerson Method . . . . . . . . . . . . . . . . . . . . 423
16.4 Maximum Capacity Augmentation . . . . . . . . . . . . . . . . 424
16.5 Shortest Path Augmentation . . . . . . . . . . . . . . . . . . . 426
16.6 Dinic’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 429
16.7 The MPM Algorithm . . . . . . . . . . . . . . . . . . . . . . . 431
16.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
16.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 436
Chapter 17 Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . .437
17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
17.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
17.3 The Network Flow Method . . . . . . . . . . . . . . . . . . . . 440
17.4 The Hungarian Tree Method for Bipartite Graphs . . . . . . . 441
17.5 Maximum Matching in General Graphs . . . . . . . . . . . . . 443
17.6 An O ( n2.5)Algorithm for Bipartite Graphs . . . . . . . . . . . 450
17.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
17.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 457
PART 7 Techniques in Computational Geometry 459
Chapter 18 Geometric Sweeping 463
18.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
18.2 Geometric Preliminaries . . . . . . . . . . . . . . . . . . . . . . 465
18.3 Computing the Intersections of Line Segments . . . . . . . . . 467
18.4 The Convex Hull Problem . . . . . . . . . . . . . . . . . . . . . 471
18.5 Computing the Diameter of a Set of Points . . . . . . . . . . . 474
18.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
18.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 480
Chapter 19 Voronoi Diagrams 481
19.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
19.2 Nearest-Point Voronoi Diagram . . . . . . . . . . . . . . . . . . 481
19.2.1 Delaunay triangulation . . . . . . . . . . . . . . . . . . 484
Construction of the Voronoi diagram . . . . . . . . . . . 486
19.3 Applications of the Voronoi Diagram . . . . . . . . . . . . . . . 489
19.3.1 Computing the convex hull . . . . . . . . . . . . . . . . 489
19.3.2 All nearest neighbors . . . . . . . . . . . . . . . . . . . . 490
19.3.3 The Euclidean minimum spanning tree . . . . . . . . . . 491
19.4 Farthest-Point Voronoi Diagram . . . . . . . . . . . . . . . . . 492
19.4.1 Construction of the farthest-point Voronoi diagram . . . 493
19.5 Applications of the Farthest-Point Voronoi Diagram . . . . . . 496
19.5.1 All farthest neighbors . . . . . . . . . . . . . . . . . . . 496
19.5.2 Smallest enclosing circle . . . . . . . . . . . . . . . . . . 497
19.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
19.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . 499
Bibliography. . . . . . . . . . . . . . . . . . . . . . . . . 501
Index . . . . . . . . . . . . . . . . . . . . . . . . .511
