Worst-Case Optimal Covering of Rectangles by Disks

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 $λ\geq 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 $λ\times 1$. We show that there is a threshold value $λ_2 = \sqrt{\sqrt{7}/2 - 1/4} \approx 1.035797\ldots$, such that for $λ<λ_2$ the critical covering area $A^*(λ)$ is $A^*(λ)=3π\left(\frac{λ^2}{16} +\frac{5}{32} + \frac{9}{256λ^2}\right)$, and for $λ\geq λ_2$, the critical area is $A^*(λ)=π(λ^2+2)/4$; these values are tight. For the special case $λ=1$, i.e., for covering a unit square, the critical covering area is $\frac{195π}{256}\approx 2.39301\ldots$. The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.

No reviews yet.

No comments yet.