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