Iterative algorithms for constructing the thinnest coverings of convex polyhedra by sets of different balls

P. D. Lebedev ; A. L. Kazakov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 27 (2021) no. 1, pp. 116-129

Résumé

In control theory and various areas of applied mathematics, it is important to approximate sets of complex geometry by unions of simple unified bodies. One of the most common methods here is covering sets with balls. In the classical statement, all the balls are equal; nevertheless, a more general statement is also of interest when the balls can be different. In this paper, we study the problem of constructing a covering of a compact set $M$ in three-dimensional Euclidean space by a set of a given number of balls whose radii are equal to the product of a common parameter $r$ and an individual positive coefficient. The optimality criterion is the minimum of $r$. We propose heuristic algorithms for constructing such coverings based on splitting the set $M$ into zones of influence of points and finding their Chebyshev centers. Statements about the properties of these algorithms are proved, and the algorithms are implemented. The problems of covering a cube with different sets of balls of two types are solved numerically. Possible directions of further research are outlined and discussed.

Détail

Keywords: optimization, ball covering, Chebyshev center, computational experiment.
Mots-clés : heuristic algorithm