1 The Power of Grids - Computing the Minimum Disk Containing \(k\) Points

Theorem 1.2.3 For set P of n points in the plane, one can compute the closest pair of P in expected linear time.

2 Quadtrees - Hierarchical Grids

3 Well Separated Pairs Decomposition

The Well-Separated Pair Decomposition and Its Applications

3.1.1 The construction algorithm

4 Clustering - Definitions and Basic Algorithms

4.2 On \(k\)-center clustering

The \(k\)-center clustering is NP-Hard.

A simple 2-approximation algorithm

4.3 On \(k\)-median clustering

4.4 On \(k\)-means clustering

5 On Complexity, Sampling, and \(\epsilon\)-Nets and \(\epsilon\)-Samples