# Geometric Approximation Algorithms

# 1 The Power of Grids - Computing the Minimum Disk Containing 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 -center clustering

The -center clustering is NP-Hard.

A simple 2-approximation algorithm