My question is related to this one

Minimize number of circles to cover set of points

In a 2D space, I have a set of points. I can deploy up to $k$ circles with radius $r$ to the space, and my goal is to maximize the number of points that will be put inside these circles. There are two cases: a) Either the circles cannot overlap b) Or they can.

I am completely stuck here. I appreciate your help.


1 Answer 1


Here is a start (for the case where you allow overlap):

For every point $v$, start by drawing a circle with radius $r$ such that $v$ is at its center.

Now, observe the following nice property: Let $d$ be a point in space such that it is contained in $m$ of the drawn circles. Then, placing a circle with radius $r$ with its middle at $d$ would cover those $m$ points.

Hence, your algorithm should start by "drawing" the $n$ circles, and applying an algorithm to find all intersections between the drawn triangles and to get the number of intersections in them.


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.