# Find circles that completely cover a polygon minimizing the amount of space covered outside the polygon

I have an arbitrary polygon that I need to roughly represent using circles. Any point inside the polygon must lie inside a circle.

There will be points outside the polygon that will fall under a circle. I want to minimize this as much as possible. I believe there will be a trade off between the number of circles used and the amount of space covered outside the polygon.

I am limited to the number of circles I can use. It will be in the order of 1 to 10. Ideally I would like an algorithm that takes the number of circles and gives me ideal positions and radius'

Here is the simplest solution. Place a circle at the center of the polygon with a radius equal to the furthest point from the center. It looks something like this:

Ideally I would like something like this:

Is there an algorithm to solve a problem like this? Does this problem have a name?

For context I am working with GeoFences which can be defined as points with a radius. The solution needs to know when you enter the polygon.

• Are your polygons all nearly rectangular like the one above, or any polygon imaginable? Commented Aug 26, 2014 at 2:01
• You may want to look up collision detection, because that's essentially the problem you're trying to solve. Approximating shapes with circles is just one method, but you might find an existing algorithm that works well for you. Commented Aug 26, 2014 at 2:11
• @forallepsilon they are arbitrary shapes representing areas on a map. Commented Aug 26, 2014 at 2:14
• Did you ever find a solution? I have a very similar proglem.
– fbl
Commented May 21, 2016 at 14:57