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

From paper "On the Discrete Unit Disk Cover Problem" by Gautam K. Das et. al.:

Minimum Geometric Disk Cover. In the minimum geometric disk cover problem, the input consists of a set of points in the plane, and the problem is to find a set of unit disks of minimum cardinality whose union covers the points. Unlike DUDC, disk centers are not constrained to be selected from a given discrete set, but rather may be centered at arbitrary points in the plane. Again, this problem is NP-hard [9] and has a PTAS solution [11, 12].

References:

9. R. Fowler, M. Paterson and S. Tanimoto, Optimal packing and covering in the plane are NP-complete, Information Processing Letters, vol 12, pp. 133-137, 1981.
10. G. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. on Computing, vol 16, pp. 1004-1022, 1987.
11. T. Gonzalez, Covering a set of points in multidimensional space, Information Processing Letters, vol 40, pp. 181-188, 1991.
12. D. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, J. ACM, vol 32, pp. 130-136, 1985.

Answer 2

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 3

Tile then jiggle

1. TILE: Find the rectangle enclosing all points
2. Tile the rectangular area with circles spaced r * sqrt(2) apart.
3. For every point calculate which circles they are and what points are in each circle.
4. Remove any circle without points.
5. Remove any circle containing only points that are contained in more than one circle.
6. Repeat 5 until there are no more.
7. Jiggle: For each circle: try moving it to see if it can cover its original points plus a max of new points and do so.
8. Do 4 and 5 again.
9. Repeat 7 until jiggling does not change which circles points are in or time exhausted.

Step 2, the tiling could be optimised by stepping trough each point and calculating/keeping only those circles that would contain a point if the tiling would be very sparse.

Answer 4

I realise that circles do not have to be centred at the points and so calculate all circles that go through any combination of two points, including circles centred at each point. I then find which points each circle covers and use a greedy algorithm to find a minimal set of circles to cover all points, but again, it may not be the minimal set of circles but is fairly easy to compute.

from collections import namedtuple
from itertools import product
from math import sqrt
from pprint import pprint as pp

Pt = namedtuple('Pt', 'x, y')
Cir = namedtuple('Cir', 'x, y, r')

def circles_from_p1p2r(p1, p2, r):
    'Following explanation at http://mathforum.org/library/drmath/view/53027.html'
    (x1, y1), (x2, y2) = p1, p2
    if p1 == p2:
        #raise ValueError('coincident points gives infinite number of Circles')
        return None, None
    # delta x, delta y between points
    dx, dy = x2 - x1, y2 - y1
    # dist between points
    q = sqrt(dx**2 + dy**2)
    if q > 2.0*r:
        #raise ValueError('separation of points > diameter')
        return None, None
    # halfway point
    x3, y3 = (x1+x2)/2, (y1+y2)/2
    # distance along the mirror line
    d = sqrt(r**2-(q/2)**2)
    # One answer
    c1 = Cir(x = x3 - d*dy/q,
             y = y3 + d*dx/q,
             r = abs(r))
    # The other answer
    c2 = Cir(x = x3 + d*dy/q,
             y = y3 - d*dx/q,
             r = abs(r))
    return c1, c2

def covers(c, pt):
    return (c.x - pt.x)**2 + (c.y - pt.y)**2 <= c.r**2

if __name__ == '__main__':
    for r, points in [(3, [Pt(*i) for i in [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]]),
                      (2, [Pt(*i) for i in [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]]),
                      (3, [Pt(*i) for i in [(-5, 5), (-4, 4), (3, 2), (1, -1), (-3, 2), (4, -2), (6, -6)]])]:
        n, p = len(points), points  
        # All circles between two points (which can both be the same point)
        circles = set(sum([[c1, c2]
                           for c1, c2 in [circles_from_p1p2r(p1, p2, r) for p1, p2 in product(p, p)]
                           if c1 is not None], []))
        # points covered by each circle 
        coverage = {c: {pt for pt in points if covers(c, pt)}
                    for c in circles}
        # Ignore all but one of circles covering points covered in whole by other circles
        #print('\nwas considering %i circles' % len(coverage))
        items = sorted(coverage.items(), key=lambda keyval:len(keyval[1]))
        for i, (ci, coveri) in enumerate(items):
            for j in range(i+1, len(items)):
                cj, coverj = items[j]
                if not coverj - coveri:
                    coverage[cj] = {}
        coverage = {key: val for key, val in coverage.items() if val}
        #print('Reduced to %i circles for consideration' % len(coverage))

        # Greedy coverage choice
        chosen, covered = [], set()
        while len(covered) < n:
            _, nxt_circle, nxt_cov = max((len(pts - covered), c, pts)
                                         for c, pts in coverage.items())
            delta = nxt_cov - covered
            covered |= nxt_cov
            chosen.append([nxt_circle, delta])

        # Output
        print('\n%i points' % n)
        pp(points)
        print('A minimum of circles of radius %g to cover the points (And the extra points they covered)' % r)
        pp(chosen)

The output showing the three runs is:

5 points
[Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=4, y=5), Pt(x=2, y=4), Pt(x=0, y=3)]
A minimum of circles of radius 3 to cover the points (And the extra points they covered)
[[Cir(x=2.958039891549808, y=2.5, r=3),
  {Pt(x=4, y=5), Pt(x=0, y=3), Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=2, y=4)}]]

5 points
[Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=4, y=5), Pt(x=2, y=4), Pt(x=0, y=3)]
A minimum of circles of radius 2 to cover the points (And the extra points they covered)
[[Cir(x=1.9364916731037085, y=2.5, r=2),
  {Pt(x=0, y=3), Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=2, y=4)}],
 [Cir(x=4, y=5, r=2), {Pt(x=4, y=5)}]]

7 points
[Pt(x=-5, y=5),
 Pt(x=-4, y=4),
 Pt(x=3, y=2),
 Pt(x=1, y=-1),
 Pt(x=-3, y=2),
 Pt(x=4, y=-2),
 Pt(x=6, y=-6)]
A minimum of circles of radius 3 to cover the points (And the extra points they covered)
[[Cir(x=3.9951865152835286, y=-0.8301243435223524, r=3),
  {Pt(x=3, y=2), Pt(x=1, y=-1), Pt(x=4, y=-2)}],
 [Cir(x=-2.0048134847164714, y=4.830124343522352, r=3),
  {Pt(x=-4, y=4), Pt(x=-3, y=2), Pt(x=-5, y=5)}],
 [Cir(x=6.7888543819998315, y=-3.1055728090000843, r=3), {Pt(x=6, y=-6)}]]

Answer 5

I'm not sure if this is correct, but if we do not need the exact locations of the solution-circles, it seems to me that we may be able to solve this by looking at point-clusters: in any of the solution-circles, the distance between any two points ought to be less than or equal to 2*r.

Algorithm:

1. j_random_hacker indicated that any solution-circle could be shifted so that
   two of its covered-points lay on its circumference without changing the 
   original covered-points. Since the solution-circle radius is given, for each 
   point: (a) calculate potential circle-centers using the point, radius, and 
   each other point that is at a distance of 2*r or less, (b) for each circle, 
   list the cluster of points that it could cover. Sort each cluster and, for
   each point, remove duplicate clusters. 

2. For each cluster group in 1., choose the cluster that has the greatest point-
   count, that is, the cluster that is most shared.

3. Remove duplicates and clusters that are sub-sequences of other clusters 
   from 2., and present the resulting size of 2. (perhaps together with the 
   chosen clusters) as the solution.

Output for equilateral triangle, r=3, [(0,0),(5.196152422706632,3),(5.196152422706632,-3)]

*Main> solve
(2,[[(0.0,0.0),(5.196152422706632,3.0)],[(0.0,0.0),(5.196152422706632,-3.0)]])

Output for Paddy3118's example, r=3, [(1,3),(0,2),(4,5),(2,4),(0,3)]:

*Main> solve
(1,[[(0.0,2.0),(0.0,3.0),(1.0,3.0),(2.0,4.0),(4.0,5.0)]])

Output for r=3, [(-5,5),(-4,4),(3,2),(1,-1),(-3,2),(4,-2),(6,-6)]:

*Main> solve
(3,[[(-5.0,5.0),(-4.0,4.0),(-3.0,2.0)],[(1.0,-1.0),(3.0,2.0),(4.0,-2.0)],
    [(4.0,-2.0),(6.0,-6.0)]])

Haskell Code:

import Data.List (delete, nub, nubBy, isInfixOf, sort, sortBy, maximumBy)

points = [(0,0),(5.196152422706632,3),(5.196152422706632,-3)]--[(1,3),(0,2),(4,5),(2,4),(0,3)]--[(-5,5),(-4,4),(3,2),(1,-1),(-3,2),(4,-2),(6,-6)]
r = 3
twoR = 2*r

circleCenters (x1,y1) (x2,y2) =
  let q = sqrt $ (x2-x1)^2 + (y2-y1)^2
      (x3, y3) = ((x1+x2)/2,(y1+y2)/2)
      first = (x3 + sqrt(r^2-(q/2)^2)*(y1-y2)/q, y3 + sqrt(r^2-(q/2)^2)*(x2-x1)/q)
      second = (x3 - sqrt(r^2-(q/2)^2)*(y1-y2)/q, y3 - sqrt(r^2-(q/2)^2)*(x2-x1)/q)
  in [first,second]

isInCircle (center_x,center_y) (x,y) = (x-center_x)^2 + (y - center_y)^2 <= r^2

findClusters (px,py) = 
  nub [sort $ [(px,py)] ++ filter (isInCircle a) potentialPoints | a <- potentialCircleCenters]
    where
      potentialPoints = filter (\(x,y) -> (x-px)^2 + (y-py)^2 <= twoR^2) (delete (px,py) points)
      potentialCircleCenters = concatMap (circleCenters (px,py)) potentialPoints

solve = (length bestClusters, bestClusters) where
  clusters = map findClusters points
  uniqueClusters = nub . concat $ clusters
  bestClusterForEachPoint = map (maximumBy (\a b -> compare (length a) (length b))) clusters
  bestClusters = nub . nubBy (\a b -> isInfixOf a b) . sortBy (\a b -> compare (length b) (length a)) 
                 $ bestClusterForEachPoint

Answer 6

This is my first answer which I will leave up as it is referred to by another answer. But see my later answer that considers circles between two points rather than this. Here is a greedy algorithm coded in Python that will find a minima but I do not know if it is the minimal solution.

dbg = False
if not dbg:
    r, n = (int(s) for s in input('r n: ').split())
    points = p = [ tuple(int(s) for s in input('x%i y%i: ' % (i, i)).split())
                   for i in range(n) ]
else:
    r, n, points = 3, 5, [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]; p = points

# What a circle at each point can cover
coverage = { i: frozenset(j
                          for j in range(i, n)
                          if (p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2 <= r**2)
             for i in range(n)}

# Greedy coverage choice
chosen, covered = [], set()
while len(covered) < n:
    # Choose the circle at the point that can cover the most ADDITIONAL points.
    _, nxt_point, nxt_cov = max((len(pts - covered), i, pts)
                                for i, pts in coverage.items())
    covered |= nxt_cov
    chosen.append(nxt_point)
print('Cover these points:\n  %s' % '\n  '.join('%s, %s' % p[i] for i in chosen))

And here is a sample run:

r n: 3 5
x0 y0: 1 3
x1 y1: 0 2
x2 y2: 4 5
x3 y3: 2 4
x4 y4: 0 3
Cover these points:
  1, 3
  4, 5

Note: the data i/o is rudimentary but the algo should be clear

Answer 7

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.

Answer 8

If circle with center C(cx, cy) covers point P(px, py) then distance |CP| < r (r - radius). So region where center of circle could be that covers point P is circle with center in P and radius r. Now lets draw all circles with centers in given points and radius r. If some circles intersects then we can draw new circle with center in such intersection that covers corresponding points. So for every pair of input points we check if circles intersects.

Suppose input points are vertices and intersection gets edge between them. Now we have a known graph problem minimum edge covering http://en.wikipedia.org/wiki/Edge_cover that could be solved in polynomial time (although with limitation n < 20 brute force probably would be acceptable)

UPDATE. That's not edge cover. My mistake.

Answer 9

If you place n circles (of radius r) all centered at each point, the find regions/points of maximum overlap and place new circles (of radius r) centered in that region. I'm not sure if this is the best way of solving the solution (if this is a way to solve it, besides the brute force way), I'm sure you can implement it with a quite a decent amount of math, and thus lowering the run-time complexity of your solution. Hope this helps. Please give feedback.