# Cover $n$ points in the plane with $k$ circles of radius $1$

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.

• 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.... Commented Jan 9, 2018 at 14:22
• @DavidRicherby Edited the question to reflect my previous comment. Commented Jan 9, 2018 at 15:01
• 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. Commented Jan 9, 2018 at 15:47
• @DavidRicherby Ah, of course very true. Thanks! Commented Jan 9, 2018 at 15:56

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.
• You definitely don't need more than $k$ circular disks, of any radius, to cover any $k$ points. Commented Jan 9, 2018 at 15:22