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

Autor(es)

Birgin, E. G. ^[1] ; Laurain, A. ^[2] ; Massambone, R. ^[1] ; Santana, A. G. ^[1]

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: SIAM JOURNAL ON SCIENTIFIC COMPUTING; v. 43, n. 3, p. A2047-A2078, 2021.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 18/24293-0 - Métodos computacionais de otimização
• Beneficiário: Sandra Augusta Santos
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 19/25258-7 - Uma abordagem de otimização contínua para o problema de cobertura
• Beneficiário: Rafael Massambone de Oliveira
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado