Minimum number of circles with radius r to cover n points

Question

What is the minimum number of circles with radius r needed to cover all n points? r and n will be given as input, followed by n pairs of integers representing the x-y co-ordinates of the n points. r is a real number and greater than 0. n is < 20.

A circle covers a point if the point lies inside the circle. A point lies inside a circle if the distance between the point and the center of the circle is less than or equal to r.

Answer 1

This is not the best solution probably but and attempt to optimize it.

Algorithm is based on random sampling:

1. Generate N circles on the map
2. Remove all circles that are not covering any point
3. Sort circles descending by number of covered points
4. Foreach circle (sorted) - mark points that are covered by circle as covered. If circle is not covering any new points remove from the list.

Here is code you can preview it live: http://jsfiddle.net/rpr8qq4t/ example result (13 circles per 30 points):

Parametrizations:

  var POINTS_NUMBER = 30;   var RADIUS = 50;   var SAMPLE_COUNT = 400; 

Some optimizations may be added to it (for example some circles can be excluded from the list too early)

Edit:

1. Change in step 1 brings better results: Generate N circles for each point (circles that covers at least on point) New version: http://jsfiddle.net/nwvao72r/3/

Edit 2 (final algorithm)

Finally:

1. Foreach point generate N=10 circles in random distance less than R from point (radius of circle so we are sure that for each circle at least one point belongs to it and each point belongs to at least one circle)
2. Repeat until all points are covered:
   • get circle covering max number of uncovered points. Mark points as covered.

Here is the version that brings best results for me, you can check it here http://jsfiddle.net/nwvao72r/4/ on average 12 circles per 30 points here.

Answer 2

I'm certain this problem is NP-hard, though I'm not going to try and prove that here.

If it is NP-hard, then to find a guaranteed-optimal solution I recommend the following approach:

1. Find all "good" potential circle placements, and for each record which points are contained in it.
2. Solve the set cover problem with these sets of points. (This problem is NP-hard.)

Good circle placements

Given any 2 points less than 2r apart, there are exactly two circles of radius r that go through these points:

[EDIT: My original description of "best-possible" circles was wrong, although this doesn't lead to problems -- thanks to commenter george for describing the right way to think about this.]

If a circle covers a maximal set of points (meaning that the circle cannot be repositioned to cover the same set of points plus at least 1 more), then that circle can be slid around until its boundary touches exactly two of the points it covers -- say, by sliding it left until it touches an already-covered point, and then rotating it clockwise around this touched point until it touches another already-covered point. This moved circle will cover exactly the set of points that the original circle covered. Furthermore we never need to consider circles that cover non-maximal sets of points, because a maximal circle covering these points and more is at least as useful and costs no more. This means that we only ever need to consider circles that touch two points. Provided we generate both circles for each sufficiently-close pair of points in the input, we will have generated all the circles we could potentially need.

So our pool of potential circles contains at most 2 circles per pair of points, for a maximum of n*(n-1) potential circles overall. (There will usually be fewer, because some pairs of points will usually be further than 2r apart and thus cannot be covered by a single circle of radius r.) In addition we need an extra circle for each point that is further than 2r from any other point -- these circles might as well be centred on those remote points.

Set cover

All we actually care about is the set of points covered by each potential circle. So for each potential circle, find the points it covers. This can be done in O(n^3) time overall, using an O(n) pass for each potential circle. To speed things up slightly, if we find that two different circles cover exactly the same set of points, we only need to keep one of these circles (sets of covered points). Also we can discard any covered point set that is a subset of some other covered point set -- it is always preferable to choose the larger covered point set in this case.

Finally we have a collection of covered point sets, and we want to find the minimum subset of these sets that covers every point. This is the set cover problem. I don't know of a specific algorithm to solve this, but branch and bound is the standard approach for such problems -- it's frequently much faster than a simpler exhaustive backtracking search. I would first prime the search by finding one (or more) heuristic solutions first, hopefully yielding a good upper bound that will reduce branch and bound search time. I think even the best algorithms for this take exponential time in the worst case, though I think that will be manageable for n < 20 as there at most 19*18 = 342 different sets of points.