| Full text | |
| Author(s): |
Total Authors: 4
|
| Affiliation: | [1] Univ Sao Paulo, Inst Math & Stat, Dept Comp Sci, Rua Matao 1010, BR-05508090 Sao Paulo, SP - Brazil
[2] Univ Sao Paulo, Inst Math & Stat, Dept Appl Math, Rua Matao 1010, BR-05508090 Sao Paulo, SP - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | SIAM JOURNAL ON SCIENTIFIC COMPUTING; v. 43, n. 3, p. A2047-A2078, 2021. |
| Web of Science Citations: | 0 |
| Abstract | |
We investigate the problem of covering a region in the plane with the union of m identical balls of minimum radius. The region to be covered may be disconnected, be nonconvex, have Lipschitz boundary, and in particular have corners. Nullifying the area of the complement of the union of balls with respect to the region to be covered is considered as the constraint, while minimizing the balls' radius is the objective function. The first-order sensitivity analysis of the area to be nullified in the constraint is performed using shape optimization techniques. Bi-Lipschitz mappings are built to model small perturbations of the nonsmooth shape defined via unions and intersections; this allows us to compute the derivative of the constraint via the notion of shape derivative. The considered approach is fairly general and can be adapted to tackle other relevant nonsmooth shape optimization problems. By discretizing the integrals that appear in the formulation of the problem and its derivatives, a nonlinear programming problem is obtained. From the practical point of view, the region to be covered is modeled by an oracle that, for a given point, answers whether it belongs to the region or not. No additional information on the region is required. Numerical examples in which the nonlinear programming problem is solved with an augmented Lagrangian approach are presented. The experiments illustrate the wide variety of regions whose covering can be addressed with the proposed 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: | 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 |
| 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 |