Finding a cover of a set of points with circles

Question

I have N points in a set V given by their coordinates and a number K (0 < K < N). I need to determine K circles (disks) with the same radius R, with their centers in points in the V set. These circles have to 'cover' all the N points and R is the smallest possible.

Can anyone help me with this?

Answer 1

This problem is known as the (discrete) $k$-center problem, and is a well known problem in clustering. While the problem is in general NP-complete, there is a very easy algorithm that generates a solution within factor 2 of the optimal solution in any metric (including the implied 2-D Euclidean distance of the question). It is due to Gonzalez, and is as follows

1. Pick any point
2. Find its farthest neighbor
3. Find the point furthest from these two
4. and so on, till you have k points.

The radius R you end up with is the distance from this last point to the next farthest point. By construction, you are guaranteed to cover all points with disks of radius centered at each of the k points, and by triangle inequality this R is within a factor of 2 of the optimal radius.

If you know that you're in the plane, you can do somewhat better in theory (including getting an exact algorithm in time polynomial in n and exponential in k), but in practice the above algorithm is likely to be the easiest

Answer 2

The problem you described is an instance of a more general optimization problem known as the covering problem, which can be solved with a linear programming relaxation. You might be able to define a cost function that is linear in the radius R of your circles (e.g. the sum of the radii for all the circles), and in indicator variables that select what points are chosen to draw the circles. This cost function would be defined subject to constraints that force the circles to cover all the points in your set (check the Wikipedia article on LP for examples)

Once you have defined the cost function and the constraints, there are several solvers (many of them free) that you can use to solve the optimization problem.