# 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.... – Skillzore Jan 9 '18 at 14:22
• @DavidRicherby Edited the question to reflect my previous comment. – Skillzore Jan 9 '18 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. – David Richerby Jan 9 '18 at 15:47
• @DavidRicherby Ah, of course very true. Thanks! – Skillzore Jan 9 '18 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. – Yuval Filmus Jan 9 '18 at 15:22