Optimal covering of solid bodies by spheres via the hyperbolic smoothing technique
Helder Manoel Venceslau, Daniela Cristina Lubke, Adilson Elias Xavier · Optimization methods & software · 2014
We consider the problem of optimally covering solid bodies by a given number of spheres. The mathematical modelling of this problem leads to a min–max–min formulation which, in addition to its intrinsic multi-level nature, has the significant characteristic of being non-differentiable. The use of the hyperbolic smoothing technique engenders a simple one-level nonlinear programming problem and allows overcoming the main difficulties presented by the original one. To illustrate the performance of the method we present computational results for two large test covering problems with up to 1,200,000 voxels. The first problem is the covering of a ring torus whose optimal solution is known whenever the number of covering spheres is small, and the second problem is a generic test problem.