Bounds on the Optimal Radius When Covering a Set with Minimum Radius Identical Disks
研究了用固定数量的最小半径相同圆盘覆盖二维有界集合的问题，给出了非光滑区域最优半径的界及其渐近展开，并通过数值实验验证了理论收敛速度。
The problem of covering a two-dimensional bounded set with a fixed number of minimum-radius identical disks is studied in the present work. Bounds on the optimal radius are obtained for a certain class of nonsmooth domains, and an asymptotic expansion of the bounds as the number of disks goes to infinity is provided. The proof is based on the approximation of the set to be covered by hexagonal honeycombs and on the thinnest covering property of the regular hexagonal lattice arrangement in the whole plane. The dependence of the optimal radius on the number of disks is also investigated numerically using a shape-optimization approach, and theoretical and numerical convergence rates are compared. An initial point construction strategy is introduced, which, in the context of a multistart method, finds good-quality solutions to the problem under consideration. Extensive numerical experiments with a variety of polygonal regions and regular polygons illustrate the introduced approach. Funding: This work was supported by Fundação de Amparo à Pesquisa do Estado de São Paulo [Grants 2013/07375-0, 2016/01860-1, 2018/24293-0, and 2019/25258-7] and Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 302682/2019-8, 303243/2021-0, 304258/2018-0, and 408175/2018-4].