论文标题
磁盘对矩形的最佳最佳覆盖
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$. 我们表明，有一个阈值$λ_2= \ sqrt {\ sqrt {7}/2-1/4} \大约1.035797 \ ldots $，因此对于$λ<λ_2$ $ a^*（λ）=3π\ left（\ frac {λ^2} {16} +\ frac {5} {32} {32} +\ frac {9} {256λ^2} \ right）$这些值很紧。 对于特殊情况$λ= 1 $，即，对于覆盖单元正方形，关键覆盖区为$ \ frac {195π} {256} {256} \大约2.39301 \ ldots $。该证明使用手动和自动分析的仔细组合，证明了使用的间隔算术技术的功能。
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.
