Worst-Case Optimal Covering of Rectangles by Disks
Sándor P. Fekete, Gupta, Utkarsh, Phillip Keldenich, Christian Scheffer, Shah, Sahil · arXiv (Cornell University) · 2020
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 $λ