Geometric Approximation Algorithms
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