PDFLINK |

# Shape Optimization for Covering Problems

Communicated by *Notices* Associate Editor Reza Malek-Madani

In his 1915 pioneering paper Nev15, Neville describes a game played at fairs where a large disk is painted on a cloth and five smaller, identical circular disks of thin metal are available. An award is offered to the person who is able to completely cover the large disk with the small disks. Neville then proceeds to show that the problem can be modeled by a system of nonlinear equations, and discusses a numerical method for an approximation of the solution. He also provides a figure for the covering of a large disk with five small disks that looks identical to the solution obtained with our algorithm shown in Figure 1. Many other works followed that dealt with the problem of covering a disk with smaller disks of minimum radius or a convex body with smaller homothetic copies. In general, planar geometry techniques are used in these works to, given a fixed and small number of disks, find the optimal radius or a bound for the optimal radius. See, for example, Kro93 and the references therein.

Nowadays, this type of problem is called a *covering problem*. The covering of the whole space with minimally overlapping identical balls has often been investigated in parallel to the problem of packing nonoverlapping spheres with the highest possible density -dimensionalCS99. It is well-known that the optimal covering of the plane is achieved by the hexagonal lattice, which realizes the *thinnest covering*, i.e., the plane covering with the least possible density of disk intersection; see Figure 2.

The covering of a bounded set with overlapping identical balls minimizing the number of balls with a fixed radius, or minimizing their radius with a fixed number of balls, as in Figure 3 in two dimensions, also represents a challenging question with a wide variety of practical applications, ranging from the configuration of a gamma ray machine radiotherapy equipment unit LMZ09 to the placement of base stations DDNS06. Compared to the problem of covering the whole space, in which case the solution is a lattice, covering a bounded set naturally yields a less regular solution, as the covering depends on the shape of the covered set. Numerical investigations hence play an important role in studying such problems. The covering of specific shapes such as squares, rectangles, disks, triangles, and polygons with a fixed number of small disks has naturally been the focus of various papers on this topic; see for instance HM97.

### Shape optimization approach

Even though various numerical methods have been introduced to solve the covering problem, the natural approach of considering the shape of the union of balls as the optimization variable has been generally overlooked, except in a few specific cases, see for instance HLE03. In this framework, the tools of *shape optimization* and *shape calculus* are employed to investigate the sensitivity with respect to variations of the union of balls, as the balls’ centers or radii are perturbed.

Shape optimization is the study of optimization problems where the variable is a geometric object, such as a subset of or a manifold; see SZ92. The shape sensitivity analysis is usually performed using strong regularity conditions on the geometry, in order to parameterize the perturbation of the geometry to compute derivatives. For instance, one often works with sets of class with i.e., sets whose boundary can be locally represented by a function of class , Still, many relevant shape optimization problems depend on mildly nonsmooth shapes such as curvilinear polygons, which means that their boundary is a union of smooth curves and it can have vertices. The covering of a set . may be naturally formulated as a nonsmooth shape optimization problem, since may be nonsmooth, and the union of balls covering can be seen, except for degenerate cases, as a curvilinear polygon, as shown in Figure 4.

The shape optimization viewpoint on the covering problems opens up new perspectives as the tools of shape calculus become available, which allows us to numerically handle the case of a large number of balls. We describe now the approach that we have developed in BLMS21 and BLMS22. We focus here on a description in two dimensions for the sake of simplicity, but we emphasize that the theoretical part of the shape optimization approach is relatively independent of the dimension. Let be an open bounded subset of and where , and is an open disk with center and radius We consider the problem of covering . using a fixed number

where

and

The function *shape functional* *shape derivative* SZ92. Using these techniques, we proved in BLMS21 that the partial derivatives of

where

Note that the formulas for the partial derivatives of

In order to prove these results, the main task is to build a transformation

In BLMS22 we have also computed the second-order partial derivatives

### Numerical methods and illustrations

In BLMS21, non-polygonal sets

It should also be noted that the discrete calculation of

In BLMS22, using shape calculus techniques, we obtained the formulas of the second-order partial derivatives of

for

So far we have not mentioned how the optimization problems were solved. Problem 1 is a nonlinear programming problem with a single hard-to-compute constraint. The familiar tool for solving problems of this type is the augmented Lagrangian method; see BM14. In particular, we used Algencan ABMS07 which is the implementation of an augmented Lagrangian method with safeguards. Very roughly speaking, an augmented Lagrangian method solves a sequence of subproblems in which the violation of shifted constraints is penalized. In the specific case of the augmented Lagrangian method implemented by Algencan, bound constraints are not penalized and remain in the subproblems. However, since problem 1 has no bound constraints, the subproblems that Algencan solves are unconstrained. In Algencan, leaving aside other issues such as availability of a linear system solver and subproblem size, when the subproblems are unconstrained and second derivatives of the functions defining the problem are available, the subproblems are solved with a globally convergent line search Newton’s method. For this reason we can say that the work developed in BLMS22 is an application of a shape-Newton method in a genuinely nonsmooth setting, a notable fact since Newton’s method is rarely used in shape optimization, even in smooth settings.

It should also be emphasized that we are actually seeking a global solution of problem 1. There are no practical deterministic global optimization methods that are capable of dealing with problem 1. Thus, the stochastic options remain and, among them, the most natural is to use a multistart approach. This is precisely what we did in BLMS21 and BLMS22, using randomly generated starting points. In BGL, based on hexagonal lattices, we developed a way to generate better than random starting points. With that, we managed to improve all the solutions reported in BLMS22 using fewer initial points and, consequently, with lower computational cost.

### Asymptotic analysis of the optimal radius

Following the numerical approximation of solutions of covering problems of bounded set, a theoretical question that naturally arises is the asymptotic behavior and bounds on the optimal radius, solution of problem 1, as the number of disks grows to infinity. The possibility of running numerical experiments with large

with

Kershner Ker39 pioneered the topic in 1939, providing an asymptotic result on the smallest number of disks of fixed radius that are necessary to cover an arbitrary region of the plane, a result that was improved ten years later by Verblunksy Ver49.

We have investigated a similar question recently in BGL for the covering of a general class of sets. Using honeycombs, defined as unions of

where

with the following asymptotic expansions, as

where

We also observed in all our numerical experiments that the lower bound

### Minimizing eigenvalues with respect to a union of disks

So far we have discussed several features of the covering of a bounded set with a union of

In particular, the optimization of Laplacian eigenvalues is a popular topic in mathematics as these problems are often simple and elegant to formulate, but are also challenging and require deep mathematical tools from a large spectrum of disciplines such as partial differential equations, spectral theory, and differential geometry. The celebrated Rayleigh–Faber–Krahn inequality, conjectured by Lord Rayleigh in the 19th century and proved several decades later by Faber and Krahn, states that the ball minimizes the first Dirichlet eigenvalue under a volume constraint. Since then, many shape optimization problems of this nature have been considered, such as the minimization of the

Let

The corresponding eigenfunction

and we impose the normalization condition

where

The minimizers of problem 9 produce an interesting geometrical configuration of the centers

In BFHL23 we have developed an algorithm to find approximate solutions of problem 9. The approach is similar to the method described in the previous sections for the covering problem. Here we can also compute the derivative of the eigenvalue

where

Figure 8 shows the results obtained by our algorithm for

As in the covering problem, the asymptotic behavior of

### Conclusions and future research

Shape calculus and optimization are a powerful set of techniques for the sensitivity analysis of functions depending on the geometry. There exists an extensive literature in the smooth setting, but shape calculus still requires an active development in the nonsmooth case. Nonsmooth shape optimization has a variety of relevant applications such as the modeling of evolving nonsmooth sets and the optimization of complex geometries such as the union and intersection of moving components, curvilinear polygons, tessellations, generalized Voronoi diagrams and minimization diagrams BLM23. Applied to covering problems, it provided a new perspective on the problem and allowed us to design efficient numerical methods. Here we have presented results with a union of balls of identical radius, but the shape optimization approach is versatile and union/intersection of sets of various shapes can be treated in a similar way, also in dimension greater than two.

Of particular interest is nonsmooth shape optimization involving partial differential equations, as irregular geometries appear naturally in applications. Both theoretical and numerical challenges arise in this context, one of the main issues being the singularities that appear in the corners of the domain, which need to be carefully studied and handled numerically. The eigenvalue problem presented in this notice represents a first step in this direction, and other nonsmooth shape optimization problems involving partial differential equations will be investigated in the near future.

## Acknowledgment

This work has been partially supported by FAPESP (grants 2013/07375-0, 2018/24293-0, and 2022/05803-3) and CNPq (grants 302073/2022-1, 303243/2021-0, 304258/2018-0, and 408175/2018-4). Antoine Laurain also acknowledges the support, since May 2023, of the Collaborating Researcher Program of the Institute of Mathematics and Statistics at the University of São Paulo.

## References

- [ABMS07]
- R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt,
*On augmented Lagrangian methods with general lower-level constraints*, SIAM J. Optim.**18**(2007), no. 4, 1286–1309, DOI 10.1137/060654797. MR2373302,## Show rawAMSref

`\bib{abmstango}{article}{ author={Andreani, R.}, author={Birgin, E. G.}, author={Mart\'{\i }nez, J. M.}, author={Schuverdt, M. L.}, title={On augmented Lagrangian methods with general lower-level constraints}, journal={SIAM J. Optim.}, volume={18}, date={2007}, number={4}, pages={1286--1309}, issn={1052-6234}, review={\MR {2373302}}, doi={10.1137/060654797}, }`

- [BFHL23]
- E. G. Birgin, L. Fernandez, G. Haeser, and A. Laurain,
*Optimization of the first Dirichlet Laplacian eigenvalue with respect to a union of balls*, J. Geom. Anal.**33**(2023), no. 6, Paper No. 184, 28, DOI 10.1007/s12220-023-01241-w. MR4572197,## Show rawAMSref

`\bib{MR4572197}{article}{ author={Birgin, E. G.}, author={Fernandez, L.}, author={Haeser, G.}, author={Laurain, A.}, title={Optimization of the first Dirichlet Laplacian eigenvalue with respect to a union of balls}, journal={J. Geom. Anal.}, volume={33}, date={2023}, number={6}, pages={Paper No. 184, 28}, issn={1050-6926}, review={\MR {4572197}}, doi={10.1007/s12220-023-01241-w}, }`

- [BGL]
- E. G. Birgin, J. L. Gardenghi, and A. Laurain,
*Asymptotic bounds on the optimal radius when covering a set with minimum radius identical balls*, Mathematics of Operations Research, to appear. - [BLM23]
- E. Birgin, A. Laurain, and T. Menezes,
*Sensitivity analysis and tailored design of minimization diagrams*, Math. Comp.**92**(2023), no. 344, 2715–2768, DOI 10.1090/mcom/3839. MR4628764,## Show rawAMSref

`\bib{mindiagopt}{article}{ author={Birgin, E.}, author={Laurain, A.}, author={Menezes, T.}, title={Sensitivity analysis and tailored design of minimization diagrams}, journal={Math. Comp.}, volume={92}, date={2023}, number={344}, pages={2715--2768}, issn={0025-5718}, review={\MR {4628764}}, doi={10.1090/mcom/3839}, }`

- [BLMS21]
- E. G. Birgin, A. Laurain, R. Massambone, and A. G. Santana,
*A shape optimization approach to the problem of covering a two-dimensional region with minimum-radius identical balls*, SIAM J. Sci. Comput.**43**(2021), no. 3, A2047–A2078, DOI 10.1137/20M135950X. MR4267494,## Show rawAMSref

`\bib{MR4267494}{article}{ author={Birgin, E. G.}, author={Laurain, A.}, author={Massambone, R.}, author={Santana, A. G.}, title={A shape optimization approach to the problem of covering a two-dimensional region with minimum-radius identical balls}, journal={SIAM J. Sci. Comput.}, volume={43}, date={2021}, number={3}, pages={A2047--A2078}, issn={1064-8275}, review={\MR {4267494}}, doi={10.1137/20M135950X}, }`

- [BLMS22]
- E. G. Birgin, A. Laurain, R. Massambone, and A. G. Santana,
*A shape-Newton approach to the problem of covering with identical balls*, SIAM J. Sci. Comput.**44**(2022), no. 2, A798–A824. MR4404468 - [BM14]
- E. G. Birgin and J. M. Martínez,
*Practical augmented Lagrangian methods for constrained optimization*, Fundamentals of Algorithms, vol. 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2014, DOI 10.1137/1.9781611973365. MR3186234,## Show rawAMSref

`\bib{bmbook}{book}{ author={Birgin, E. G.}, author={Mart\'{\i }nez, J. M.}, title={Practical augmented Lagrangian methods for constrained optimization}, series={Fundamentals of Algorithms}, volume={10}, publisher={Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA}, date={2014}, pages={xiv+220}, isbn={978-1-611973-35-8}, review={\MR {3186234}}, doi={10.1137/1.9781611973365}, }`

- [CS99]
- J. H. Conway and N. J. A. Sloane,
*Sphere packings, lattices and groups*, 3rd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 290, Springer-Verlag, New York, 1999. With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov, DOI 10.1007/978-1-4757-6568-7. MR1662447,## Show rawAMSref

`\bib{conway}{book}{ author={Conway, J. H.}, author={Sloane, N. J. A.}, title={Sphere packings, lattices and groups}, series={Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]}, volume={290}, edition={3}, note={With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov}, publisher={Springer-Verlag, New York}, date={1999}, pages={lxxiv+703}, isbn={0-387-98585-9}, review={\MR {1662447}}, doi={10.1007/978-1-4757-6568-7}, }`

- [DDNS06]
- G. K. Das, S. Das, S. C. Nandy, and B. P. Sinha,
*Efficient algorithm for placing a given number of base stations to cover a convex region*, Journal of Parallel and Distributed Computing**66**(2006), no. 11, 1353–1358. - [Had68]
- J. Hadamard,
*Mémoire sur le probleme d’analyse relatif a l’équilibre des plaques élastiques*, Mémoire des savants étrangers, 33, 1907, Œuvres de Jacques Hadamard, Editions du C.N.R.S., Paris, 1968, pp. 515–641. - [Hen06]
- Antoine Henrot,
*Extremum problems for eigenvalues of elliptic operators*, Frontiers in Mathematics, Birkhäuser Verlag, Basel, 2006. MR2251558,## Show rawAMSref

`\bib{MR2251558}{book}{ author={Henrot, Antoine}, title={Extremum problems for eigenvalues of elliptic operators}, series={Frontiers in Mathematics}, publisher={Birkh\"{a}user Verlag, Basel}, date={2006}, pages={x+202}, isbn={978-3-7643-7705-2}, isbn={3-7643-7705-4}, review={\MR {2251558}}, }`

- [HLE03]
- C. Ho-Lun and H. Edelsbrunner,
*Area and perimeter derivatives of a union of disks*, Computer Science in Perspective: Essays Dedicated to Thomas Ottmann (Rolf Klein, Hans-Werner Six, and Lutz Wegner, eds.), Springer Berlin Heidelberg, Berlin, Heidelberg, 2003, pp. 88–97. - [HM97]
- Aladár Heppes and Hans Melissen,
*Covering a rectangle with equal circles*, Period. Math. Hungar.**34**(1997), no. 1-2, 65–81, DOI 10.1023/A:1004224507766. 3rd Geometry Festival: an International Conference on Packings, Coverings and Tilings (Budapest, 1996). MR1608319,## Show rawAMSref

`\bib{heppes}{article}{ author={Heppes, Alad\'{a}r}, author={Melissen, Hans}, title={Covering a rectangle with equal circles}, note={3rd Geometry Festival: an International Conference on Packings, Coverings and Tilings (Budapest, 1996)}, journal={Period. Math. Hungar.}, volume={34}, date={1997}, number={1-2}, pages={65--81}, issn={0031-5303}, review={\MR {1608319}}, doi={10.1023/A:1004224507766}, }`

- [Ker39]
- Richard Kershner,
*The number of circles covering a set*, Amer. J. Math.**61**(1939), 665–671, DOI 10.2307/2371320. MR0000043,## Show rawAMSref

`\bib{kershner}{article}{ author={Kershner, Richard}, title={The number of circles covering a set}, journal={Amer. J. Math.}, volume={61}, date={1939}, pages={665--671}, issn={0002-9327}, review={\MR {0000043}}, doi={10.2307/2371320}, }`

- [Kro93]
- S. Krotoszyński,
*Covering a disk with smaller disks*, Studia Sci. Math. Hungar.**28**(1993), no. 3-4, 277–283. MR1266811,## Show rawAMSref

`\bib{kroto}{article}{ author={Krotoszy\'{n}ski, S.}, title={Covering a disk with smaller disks}, journal={Studia Sci. Math. Hungar.}, volume={28}, date={1993}, number={3-4}, pages={277--283}, issn={0081-6906}, review={\MR {1266811}}, }`

- [LMZ09]
- Leo Liberti, Nelson Maculan, and Yue Zhang,
*Optimal configuration of gamma ray machine radiosurgery units: the sphere covering subproblem*, Optim. Lett.**3**(2009), no. 1, 109–121, DOI 10.1007/s11590-008-0095-4. MR2453509,## Show rawAMSref

`\bib{liberti}{article}{ author={Liberti, Leo}, author={Maculan, Nelson}, author={Zhang, Yue}, title={Optimal configuration of gamma ray machine radiosurgery units: the sphere covering subproblem}, journal={Optim. Lett.}, volume={3}, date={2009}, number={1}, pages={109--121}, issn={1862-4472}, review={\MR {2453509}}, doi={10.1007/s11590-008-0095-4}, }`

- [Nev15]
- E. H. Neville,
*On the solution of numerical functional equations: Illustrated by an account of a popular puzzle and of its solution*, Proceedings of the London Mathematical Society**s2-14**(1915), no. 1, 308–326. - [SZ92]
- Jan Sokołowski and Jean-Paul Zolésio,
*Introduction to shape optimization*:*Shape sensitivity analysis*, Springer Series in Computational Mathematics, vol. 16, Springer-Verlag, Berlin, 1992, DOI 10.1007/978-3-642-58106-9. MR1215733,## Show rawAMSref

`\bib{MR1215733}{book}{ author={Soko\l owski, Jan}, author={Zol\'{e}sio, Jean-Paul}, title={Introduction to shape optimization}, series={Springer Series in Computational Mathematics}, volume={16}, subtitle={Shape sensitivity analysis}, publisher={Springer-Verlag, Berlin}, date={1992}, pages={ii+250}, isbn={3-540-54177-2}, review={\MR {1215733}}, doi={10.1007/978-3-642-58106-9}, }`

- [Ver49]
- S. Verblunsky,
*On the least number of unit circles which can cover a square*, J. London Math. Soc.**24**(1949), 164–170, DOI 10.1112/jlms/s1-24.3.164. MR33552,## Show rawAMSref

`\bib{verblunksy}{article}{ author={Verblunsky, S.}, title={On the least number of unit circles which can cover a square}, journal={J. London Math. Soc.}, volume={24}, date={1949}, pages={164--170}, issn={0024-6107}, review={\MR {33552}}, doi={10.1112/jlms/s1-24.3.164}, }`

## Credits

All figures, including the opening image, are courtesy of the authors.

Photo of Ernesto G. Birgin is courtesy of Bruno Datan.

Photo of Antoine Laurain is courtesy of Rosana Miliorini Souza Laurain.