Covering polygons with circles of minimal radius

Question

I have a closed polygon and I would like to fully cover it with a set of K circles of different radius such that the area covered by the circles but outside the polygon is minimal. This seems the ideal candidate for linear programming. Does anybody know a standard formulation / an algorithm for this problem?

Answer 1

This is not at all an ideal candidate for linear programming, as the objective function is quadratic in the coordinates and radii of the circles (except where a circle crosses a polygon vertex).

This problem is interesting even for the simple case of a triangle and two circles. Quadratic programming may be a good approach. The constraints will be easy to express as quadratic constraints if the following theorem is true:

For any $\triangle ABC, \odot P_1, \odot P_2$ such that the three lines $AB, AC, BC$ are each contained in $P_1 \cup P_2$, the entire interior of $\triangle ABC$ is contained in $P_1 \cup P_2$.

This theorem is probably true but I can't prove it. Note that if you use three circles instead of two, the corresponding theorem is false (consider an equilateral triangle, and three circles of diameter equal to the side length centered on the vertices).