Worst-Case Optimal Covering of Rectangles by Disks

03/18/2020
by   Sandor P. Fekete, et al.
0

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 λ_2 = √(√(7)/2 - 1/4)≈ 1.035797…, such that for λ<λ_2 the critical covering area A^*(λ) is A^*(λ)=3π(λ^2/16 +5/32 + 9/256λ^2), and for λ≥λ_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 195π/256≈ 2.39301…. The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset