Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

SHAPE OPTIMIZATION APPROACH TO THE PROBLEM OF COVERING A TWO-DIMENSIONAL REGION WITH MINIMUM-RADIUS IDENTICAL BALLS

Full text
Author(s):
Birgin, E. G. [1] ; Laurain, A. [2] ; Massambone, R. [1] ; Santana, A. G. [1]
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 type: 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 type: Research Projects - Thematic Grants
FAPESP's process: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry
Grantee:José Alberto Cuminato
Support type: 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 type: Scholarships in Brazil - Post-Doctorate