Approximation algorithm question, clustering on n points

Question

So the algorithm I thought of, is to iterate through the n points, centering a ball at each point, and keeping track of the point where we centered that encapsulated the most points. Then remove the encapsulated points from this max ball we found, then iterate through all the points again. Continue until there are no longer any points not encapsulated. Return all the centers we found.

I'm not sure if this algorithm is correct. O(1) approximation algorithm is in terms of O( $\frac{\Delta_{ours}}{\Delta}$). The requirement is a polynomial algorithm, which I believe mine is in the order of $n^{2}$.

I'm also not sure how to prove the correctness of an approximation algorithm either.

Answer 1

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}\| > 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$.