How to cover a set of circles in a plane with disjoint circles of constant radius?

Question

So you have a sheet / area of a given dimension, and within this area are holes (their center point(x,y) and radius are given). The problem is you need to cover these holes with patches. These circular patches have a fixed radius (ie: radius of 5) and are not allowed to overlap with each other (but can touch). You're allowed to use as many as you like, the goal is not to find the most optimal number, but to see if it's possible to cover every single hole.

I've solved a similar problem with a KD tree, but due to the 3D dimensional nature of the holes in this problem, I'm unsure on how to approach it. Just looking for a pointer in the right direction, not the coded solution :)

Answer 1

Depending on the sizes of the patches and the holes there may be no solution.

Solution with most compact patches array:

No solution because hole is bigger than patches, which allows uncovered areas:

No solution because holes are too close:

For a general construction you begin with a patch centered on the hole. Then translate and rotate (around the center of a contiguous patch) the patch as required:

Answer 2

You probably are looking for an analytical or at least a deterministic solution for this. But I'm afraid it's too complicated to have one. Metaheuristics like EAs, on the other hand, can cope with this kind of problems due to their stochastic nature. You have to change your problem to an optimization problem when you decide to adopt such approach.

I tried to solve this using the basic form DE algorithm. To define an optimization problem I assumed that a solution vector is a an array of 2*N floating point variables, where N is the number of holes. This array represents X and Y coordinates of patches, since N patches are needed at most to cover N holes.

The cost function (that is needed to get minimized) is defined as follows:

Find closest patch to each hole
Find A1 as sum of uncovered areas of holes by their closest patchs
Find A2 as sum of intersection areas of active(!) patches
return max(A1, A2)

In this function an active patch is a patch that is the closest one to at least one hole. This definition is added to the problem to cover the situation you mentioned in your comment to Ripi2's answer (when a patch covers two holes, so there's another patch that is useless). To be more descriptive, let's assume that there's this P1 patch that is not the closest one to any of holes. H1 is closest hole to this patch, but its closest patch is P2. So we can say for sure that intersection area of H1 and P1 is less than or equal to the one of H1 and P2. Since this is true about its closest hole, it will be the same for all other holes, so let's think that it doesn't exist!

This is a sample:

Just keep in mind that these algorithms never guarantee to find the global optimum, however, they will give a [set of] sub-optimal solution[s] at hand.