1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ Wow, that is very insightful. Thank you so much! $\endgroup$ May 12 '20 at 21:19
  • $\begingroup$ I'm curious, why be within 2$\Delta$ in order to do nothing rather than $\Delta$? If you are within 2$\Delta$, wouldn't this point p, be far enough away from any of the recorded centers, and therefore need to be added to the set of centers? $\endgroup$ May 12 '20 at 21:56
  • $\begingroup$ Try running the proof for this version of the algorithm, and see what goes wrong. $\endgroup$ May 12 '20 at 21:58
  • $\begingroup$ Hm, I think I may be misunderstanding. So I tried it with a size of n = 2. These two points are of distance > $2\Delta$ from each other. So the algorithm would add the first point to the set of centers. Then it would not add the second point to the set of centers since it is not within $2\Delta$ of any of the points in the set. So our resulting set is only 1 point, but a circle centered at it won't cover all points. $\endgroup$ May 12 '20 at 22:10
  • 1
    $\begingroup$ We add a point to the set of centers if it is not within a distance of $2\Delta$ to any of the chosen centers. $\endgroup$ May 12 '20 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.