algorithm - 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.