Minimum number of circles with radius r to cover n points

algorithm, computational-geometry

Solution

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

Algorithm is based on random sampling:

- Generate N circles on the map

- Remove all circles that are not covering any point

- Sort circles descending by number of covered points

- 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:

- 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:

- 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)

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

Problem

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.

Original source