Contents
Preface xi
Chapter 1. The Power of Grids Closest Pair and Smallest Enclosing Disk 1
1.1. Preliminaries 1
1.2. Closest pair 1
1.3. A slow 2-approximation algorithm for the k-enclosing disk 5
1.4. A linear time 2-approximation for the k-enclosing disk 6
1.5. Bibliographical notes 10
1.6. Exercises 11
Chapter 2. Quadtrees Hierarchical Grids 13
2.1. Quadtrees a simple point-location data-structure 13
2.2. Compressed quadtrees 15
2.3. Dynamic quadtrees 20
2.4. Bibliographical notes 24
2.5. Exercises 26
Chapter 3. Well-Separated Pair Decomposition 29
3.1. Well-separated pair decomposition (WSPD) 29
3.2. Applications of WSPD 33
3.3. Semi-separated pair decomposition (SSPD) 40
3.4. Bibliographical notes 43
3.5. Exercises 44
Chapter 4. Clustering Definitions and Basic Algorithms 47
4.1. Preliminaries 47
4.2. On k-center clustering 49
4.3. On k-median clustering 51
4.4. On k-means clustering 57
4.5. Bibliographical notes 57
4.6. Exercises 59
Chapter 5. On Complexity, Sampling, and ε-Nets and ε-Samples 61
5.1. VC dimension 61
5.2. Shattering dimension and the dual shattering dimension 64
5.3. On ε-nets and ε-sampling 70
5.4. Discrepancy 75
5.5. Proof of the ε-net theorem 80
5.6. A better bound on the growth function 82
5.7. Bibliographical notes 83
5.8. Exercises 84
v
Previous Page Next Page