Approximation algorithm question, clustering on n points
There's an even simpler algorithm, the greedy algorithm. This algorithm iterates through the points in some order. Initially the set of centers is empty. When point $p$ is reached, if $p$ is within distance $2\Delta$ of one of the selected centers, then we do nothing. Otherwise, we add $p$ to the set of centers. Naive implementation of this algorithm runs in time $O(kn)$, which is polynomial.

Why does this work? Suppose that balls at radius $\Delta$ centered at the points $p_{i_1},\ldots,p_{i_k}$ cover the entire set, and suppose that the algorithm above has selected points $p_{j_1},\ldots,p_{j_k}$. We have to show that every point in the set is within distance $2\Delta$ of these points.

For a point $p$, let $c(p)$ denote the point among $p_{i_1},\ldots,p_{i_k}$ which is closest to $p$.
I claim that $c(p_{j_a}) \neq c(p_{j_b})$ for $a \neq b$. Indeed, by construction $\|p_{j_a}-p_{j_b}\| &gt; 2\Delta$. But if $c(p_{j_a}) = c(p_{j_b}) = q$, then $\|p_{j_a}-p_{j_b}\| \leq \|p_{j_a}-q\| + \|q-p_{j_b}\| \leq 2\Delta$.

Renumber the points so that $c(p_{j_a}) = p_{i_a}$, and consider an arbitrary point $p$ in the set. Suppose that $c(p) = p_{i_a}$. Then $\|p-p_{j_a}\| \leq \|p-p_{i_a}\| + \|p_{i_a}-p_{j_a}\| \leq 2\Delta$.