I am studying for an algorithms exam and ran into this example problem.

A circular disk with radius $2r$ can be covered by $7$ circular disks with radius $r$; in the following you can use this statement without proof.

Suppose that we are given a set $S$ of $n$ points in the plane, and we want to cover all points in $S$ by a minimum number of circular disks of radius $1$. Let $k$ be the optimal number of disks needed. Propose a polynomial time algorithm to produce a covering with at most $7k$ circular disks of radius $1$.

I do understand the question but I have no idea where to begin or how to approach this. Should a reduction be used? Or is there a simple and obvious answer? How do you cover $n$ points that you know nothing about? Maybe calculate the distances between them?

I do realize that if the distance between all points is greater than $2$ units, then $k = n$ since every circle of radius $2$ can only cover a single point.

I mainly want to understand the problem so that I can attempt a solution on my own, but a solution to the problem would also be nice, so that I can check my answer later.

  • $\begingroup$ I guess "Or maybe you understand what the question is looking for but can't work out how to start answering it?" Would be close. I have no issues with the terms used in the question. I am just lost at how you would cover nodes with a fixed circle, when you know nothing about the nodes. I mean what if they are all more than 2 units apart? Then k = n i guess.... $\endgroup$
    – Skillzore
    Commented Jan 9, 2018 at 14:22
  • $\begingroup$ @DavidRicherby Edited the question to reflect my previous comment. $\endgroup$
    – Skillzore
    Commented Jan 9, 2018 at 15:01
  • $\begingroup$ Thanks! I edited your edit because it doesn't help much to write "Edit:". Most people who read your question will read it after the edit and they don't need to see the old, confusing version of the question. $\endgroup$ Commented Jan 9, 2018 at 15:47
  • $\begingroup$ @DavidRicherby Ah, of course very true. Thanks! $\endgroup$
    – Skillzore
    Commented Jan 9, 2018 at 15:56

1 Answer 1


Use a greedy algorithm to cover your points with circular disks of radius 2. In other words, repeatedly choose an uncovered point, and cover it with a circular disk of radius 2 centered at the point. Now cover each of your disks with seven disks of radius 1.

Why does this work? Suppose that you covered the points using $k$ circular disks of radius 2 centered at the points $p_1,\ldots,p_k$. It is not hard to check that the distance between any two different points $p_i,p_j$ is larger than 2 (otherwise $p_j$ would have been covered by the disk around $p_i$, assuming $i < j$), and so no circular disk of radius 1 can cover both $p_i$ and $p_j$. This implies that $k$ circular disks of radius 1 are needed to cover the points $p_1,\ldots,p_k$, and so at least $k$ are needed to cover the original set of points. The solution produced by the algorithm uses $7k$ circular disks.

  • $\begingroup$ You lost me here: "This implies that k circular disks of radius 1 are needed to cover the points p1,…,pk". Don't you need more than k circular disks of radius 1? Since disks of radius 2 might cover points that reside 1-2 units from the center? $\endgroup$
    – Skillzore
    Commented Jan 9, 2018 at 15:21
  • $\begingroup$ You definitely don't need more than $k$ circular disks, of any radius, to cover any $k$ points. $\endgroup$ Commented Jan 9, 2018 at 15:22
  • $\begingroup$ Oh, right... brain fart! How would we know that the k' (prime) disks used by our algorithm is in any way close to the k (not prime) disks used by the optimal solution? $\endgroup$
    – Skillzore
    Commented Jan 9, 2018 at 15:27
  • $\begingroup$ We don't know, and it's not necessarily true. $\endgroup$ Commented Jan 9, 2018 at 15:28
  • $\begingroup$ Then how do we know that we havn't used more then the allotted 7k (not prime) disks? I.e. that 7k' <= 7k holds true? $\endgroup$
    – Skillzore
    Commented Jan 9, 2018 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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