<p>The problem of covering $n$ points in the Euclidean plane by $k$ unit balls is a special case of your problem that is already known to be NP-complete. It is also hard to approximate the optimal covering radius better than a factor of about 1.84. See</p>

<p>N. Megiddo and K.J. Supowit. On the complexity of some common geometric loca- tion problems. SIAM J. Comput., 13:182–196, 1984.</p>

<p>T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985.</p>

<p>T. Feder and D.H. Greene. Optimal algorithms for approximate clustering. In Proc.</p>

CC BY-SA 3.0
2017-10-18T00:46:06.513Z
I think the OP is asking a different question. He is given k balls of fixed radius r and wants to maximize the # of points covered.
Chandra Chekuri
CC BY-SA 3.0
2017-10-18T17:51:29.517Z
True, but if you can't solve the decision problem (can you cover all points) you also can't solve the optimization problems (how many can you cover, or what radius do you need to cover all).
David Eppstein
CC BY-SA 3.0
2017-10-17T21:26:45.297Z
2017-10-17T21:26:45.297Z
David Eppstein
<p>For the case of disks in the plane, there is a recent PTAS:
<a href="https://arxiv.org/abs/1607.06665" rel="nofollow noreferrer">https://arxiv.org/abs/1607.06665</a>
There is also a fixed parameter tractable algorithm for this problem for spaces with bounded VC dimension - see ref in the paper. </p>

<p>For general metric spaces, it is easy to reduce the problem to set cover instance, where there is a cover with k sets covering m points, iff there are k balls covering m points. To see that, just take the set system, and build a bipartite graph, with ground elements on one side, and sets on the other side. Connect every set, to every element it covers. All edges have weight 1, and all missing edges, are assigned their shortest path distance. Clearly, in this graph, there is a coverage by k balls (of radius 1) of m points iff there are k sets covering m elements in the original set system. since 1-1/e approximation to partial set cover is the best one can hope for (I am too lazy to find the ref - but that should be well known), it follows that it is not possible in general to do better.</p>

CC BY-SA 3.0
2017-11-20T03:17:01.767Z
2017-11-20T03:17:01.767Z
Sariel Har-Peled
<p>Consider $n$ points and a distance function $d$ that satisfies the triangle inequality. We are also given a number $r$. </p>

<p>Each point $p$ defines a set $B_p$ (or a ball) that covers all other points that lie within a distance $r$ from $p$. Find $k$ sets (or balls) that covers the most number of points.</p>

<p>Obviously, we could find a $1-1/e$ approximation (via greedy) as this is a special case of the maximum $k$-set coverage problem. </p>

<p>But is there a hardness result for this problem? I would also like to consider the Euclidean distance case.</p>

CC BY-SA 3.0
2017-10-17T09:23:10.630Z
There is a PTAS, at least in 2d https://arxiv.org/abs/1702.01836
Sasho Nikolov
CC BY-SA 3.0
2017-10-17T12:53:12.130Z
If one can get better than (1-1/e) for your problem you can get the same bound for max k-coverage in arbitrary set systems - consider the reduction of set cover to dominating set in a graph.
Chandra Chekuri
<np-hardness><approximation-algorithms><covering-problems>
Geometric max cover
polar_bear_cheese
# Geometric max cover

(Asked by: username_0 on 2017-10-17)

Consider $n$ points and a distance function $d$ that satisfies the triangle inequality. We are also given a number $r$.

Each point $p$ defines a set $B\_p$ (or a ball) that covers all other points that lie within a distance $r$ from $p$. Find $k$ sets (or balls) that covers the most number of points.

Obviously, we could find a $1-1/e$ approximation (via greedy) as this is a special case of the maximum $k$-set coverage problem.

But is there a hardness result for this problem? I would also like to consider the Euclidean distance case.

**Tags:** np-hardness, approximation-algorithms, covering-problems
> **Comments:**
> **username_1**: There is a PTAS, at least in 2d https://arxiv.org/abs/1702.01836  
> **username_2**: If one can get better than (1-1/e) for your problem you can get the same bound for max k-coverage in arbitrary set systems - consider the reduction of set cover to dominating set in a graph.  

---

## 2 answers

### Answer by username_3 on 2017-10-17. Score: 3

The problem of covering $n$ points in the Euclidean plane by $k$ unit balls is a special case of your problem that is already known to be NP-complete. It is also hard to approximate the optimal covering radius better than a factor of about 1.84. See

N. Megiddo and K.J. Supowit. On the complexity of some common geometric loca- tion problems. SIAM J. Comput., 13:182–196, 1984.

T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985.

T. Feder and D.H. Greene. Optimal algorithms for approximate clustering. In Proc.

> **Comments:**
> **username_2**: I think the OP is asking a different question. He is given k balls of fixed radius r and wants to maximize the # of points covered.  
> **username_3**: True, but if you can't solve the decision problem (can you cover all points) you also can't solve the optimization problems (how many can you cover, or what radius do you need to cover all).  

---

### Answer by username_4 on 2017-11-20. Score: 2

For the case of disks in the plane, there is a recent PTAS:
<https://arxiv.org/abs/1607.06665>
There is also a fixed parameter tractable algorithm for this problem for spaces with bounded VC dimension - see ref in the paper.

For general metric spaces, it is easy to reduce the problem to set cover instance, where there is a cover with k sets covering m points, iff there are k balls covering m points. To see that, just take the set system, and build a bipartite graph, with ground elements on one side, and sets on the other side. Connect every set, to every element it covers. All edges have weight 1, and all missing edges, are assigned their shortest path distance. Clearly, in this graph, there is a coverage by k balls (of radius 1) of m points iff there are k sets covering m elements in the original set system. since 1-1/e approximation to partial set cover is the best one can hope for (I am too lazy to find the ref - but that should be well known), it follows that it is not possible in general to do better.


---

