Worst-Case Optimal Covering of Rectangles by Disks

Abstract

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 $\hat{I}»\ge 1$, the critical covering area $A^{\ast }(\hat{I}»)$ is the minimum value for which any set of disks with total area at least $A^{\ast }(\hat{I}»)$ can cover a rectangle of dimensions $\hat{I}»\times 1$. We show that there is a threshold value $\hat{I}{»}_2=\sqrt{\sqrt{7}/2-1/4}\approx 1.035797\dots$, such that for $\hat{I}»<\hat{I}{»}_2$ the critical covering area $A^{\ast }(\hat{I}»)$ is $A^{\ast }(\hat{I}»)=3\ddot{I}€\left(\frac{\hat{I}{»}^2}{16}+\frac{5}{32}+\frac{9}{256\hat{I}{»}^2}\right)$, and for $\hat{I}»\ge \hat{I}{»}_2$, the critical area is $A^{\ast }(\hat{I}»)=\ddot{I}€(\hat{I}{»}^2+2)/4$; these values are tight. For the special case $\hat{I}»=1$, i.e., for covering a unit square, the critical covering area is $\frac{195\ddot{I}€}{256}\approx 2.39301\dots$. The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.

45 pages, 26 figures. Full version of an extended abstract with the same title accepted for publication in the proceedings of the 36th Symposium on Computational Geometry (SoCG 2020)