摘要：We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any λ ⥠1, the critical covering area A^*(λ) is the minimum value for which any set of disks with total area at least A^*(λ) can cover a rectangle of dimensions λÃ- 1. We show that there is a threshold value λâ,, = â^S{â^S7/2 - 1/4} â^ 1.035797â¦, such that for λ < λâ,, the critical covering area A^*(λ) is A^*(λ) = 3Ï(λ²/16 + 5/32 + 9/(256λ²)), and for λ ⥠λâ,,, the critical area is A^*(λ)=Ï(λ²+2)/4; these values are tight. For the special case λ=1, i.e., for covering a unit square, the critical covering area is 195Ï/256 â^ 2.39301â¦. The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.
