Worst-Case Optimal Covering of Triangles by Disks

Abstract

The critical covering area of a triangle T is the value A^*(T) such that (1) each set of disks with a total area of at least A^*(T) permits a covering of T and (2) for each A^- < A^*(T), there is a set D^- of disks with a total area of A^- such that D^- cannot cover T. The critical covering coefficient C^*(T) of T is the ratio A^*(T)/|T| between the critical covering area of T and the area of T.

In this work, we prove that the critical covering coefficient for isosceles triangles with an apex angle α ≤ π/4 is π tan(α/2)/sin²(α),
and the covering coefficient for isosceles triangles with an apex angle α ≥ π/2 is π tan(α/2). The critical covering coefficient for equilateral triangles is π√3/2 ≈ 2.7207...; the comparison with the recently established critical covering coefficient for squares (195π/256 ≈ 2.39301..., as shown by Fekete et al. in 2020) indicates the additional difficulty of covering triangles. As a corollary, we obtain that π/h is the critical covering area of obtuse triangles with inner angles α₁ ≥ π/2 and π/3 ≥ α₂, α₃ and a height of h passing the corner with an inner angle of α₁.

Our proofs are constructive, i.e., we provide corresponding worst-case optimal covering algorithms.