1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\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 Jan 9 '18 at 15:21
  • $\begingroup$ You definitely don't need more than $k$ circular disks, of any radius, to cover any $k$ points. $\endgroup$ – Yuval Filmus Jan 9 '18 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 Jan 9 '18 at 15:27
  • $\begingroup$ We don't know, and it's not necessarily true. $\endgroup$ – Yuval Filmus Jan 9 '18 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 Jan 9 '18 at 15:29

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.