Advanced search
Start date
Betweenand


Bounds on the Optimal Radius When Covering a Set with Minimum Radius Identical Disks

Full text
Author(s):
Birgin, Ernesto G. ; Gardenghi, John L. ; Laurain, Antoine
Total Authors: 3
Document type: Journal article
Source: MATHEMATICS OF OPERATIONS RESEARCH; v. N/A, p. 36-pg., 2023-09-12.
Abstract

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. (AU)

FAPESP's process: 18/24293-0 - Computational methods in optimization
Grantee:Sandra Augusta Santos
Support Opportunities: Research Projects - Thematic Grants
FAPESP's process: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry
Grantee:Francisco Louzada Neto
Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
FAPESP's process: 19/25258-7 - A nonlinear optimization approach to the covering problem
Grantee:Rafael Massambone de Oliveira
Support Opportunities: Scholarships in Brazil - Post-Doctoral
FAPESP's process: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
Grantee:Reinaldo Morabito Neto
Support Opportunities: Research Projects - Thematic Grants