Geodesic
Algorithms of optimal set covering on the planar $\mathbb{R}^2 $
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 26 (2016) no. 2, pp. 258-270 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of optimal covering of planar convex sets with a union of a given number $n$ of equal disks is studied. Criterion of optimality is a minimization of disks' radius, which gives an opportunity to reduce the optimization problem to a construction of the best Chebyshev $n$-net of a convex set. Numerical methods based on dividing the set into Dirichlet zones and finding characteristic points are suggested and proved in the present paper. One of the main elements of the methods is a Chebyshev center calculation for a compact convex set. Stochastic algorithms for generating an initial position of the $n$-net points are presented. Modeling of some examples is computed and visualization of the constructed covering is realized.
Keywords: disk covering, best Chebyshev net, Chebyshev center, Dirichlet zone, characteristic points, closed curve. 
@article{VUU_2016_26_2_a11,
     author = {V. N. Ushakov and P. D. Lebedev},
     title = {Algorithms of optimal set covering on the planar $\mathbb{R}^2 $},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {258--270},
     year = {2016},
     volume = {26},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2016_26_2_a11/}
}
TY  - JOUR
AU  - V. N. Ushakov
AU  - P. D. Lebedev
TI  - Algorithms of optimal set covering on the planar $\mathbb{R}^2 $
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2016
SP  - 258
EP  - 270
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VUU_2016_26_2_a11/
LA  - ru
ID  - VUU_2016_26_2_a11
ER  - 
%0 Journal Article
%A V. N. Ushakov
%A P. D. Lebedev
%T Algorithms of optimal set covering on the planar $\mathbb{R}^2 $
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2016
%P 258-270
%V 26
%N 2
%U http://geodesic.mathdoc.fr/item/VUU_2016_26_2_a11/
%G ru
%F VUU_2016_26_2_a11
V. N. Ushakov; P. D. Lebedev. Algorithms of optimal set covering on the planar $\mathbb{R}^2 $. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 26 (2016) no. 2, pp. 258-270. http://geodesic.mathdoc.fr/item/VUU_2016_26_2_a11/

[1] Krasovskii N. N., Subbotin A. I., Positional differential games, Nauka, M., 1974, 456 pp. | MR

[2] Ushakov V. N., Lebedev P. D., Matviychuk A. R., Malev A. G., “Differential games with fixed terminal time and estimation of the instability degree of sets in these games”, Proceedings of the Steklov Institute of Mathematics, 277:1 (2012), 266–277 | DOI | MR | Zbl

[3] Mestetskii L. M., Continuous morphology of binary images: figures, skeletons, circulars, Fizmatlit, M., 2009, 288 pp.

[4] Kurzhanskii A. B., Filippova T. F., “Description of the set of viable trajectories of a differential inclusion”, Dokl. Akad. Nauk SSSR, 289:1 (1986), 38–41 (in Russian) | MR

[5] Chernous'ko F. L., Evaluation of a phase state of dynamical systems, Nauka, M., 1988, 384 pp. | MR

[6] Ushakov V. N., Matviychuk A. R., Lebedev P. D., “Defect of stability in game-pursuit problem”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2010, no. 3, 87–103 (in Russian)

[7] Ushakov V. N., Lavrov N. G., Ushakov A. V., “Construction of solutions in an approach problem of a stationary control system”, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 20, no. 4, 2014, 277–286 (in Russian) | MR

[8] Ushakov V. N., Lakhtin A. S., Lebedev P. D., “Optimization of the Hausdorff distance between sets in Euclidean space”, Proceedings of the Steklov Institute of Mathematics, 291, no. suppl. 1 (2015), 222–238 | DOI | MR | MR

[9] Garkavi A. L., “Existence of the best net and the best width for set in a Banach space”, Usp. Mat. Nauk, 15:2 (1960), 210–211 (in Russian) | MR

[10] Garkavi A. L., “On the optimal net and best cross-section of a set in a normed space”, Izv. Akad. Nauk SSSR, Ser. Mat., 26:1 (1962), 87–106 (in Russian) | MR | Zbl

[11] Kolmogorov A. N., “On some asymptotic characteristics of completely bounded metric spaces”, Dokl. Akad. Nauk SSSR, 108:3 (1956), 385–388 (in Russian) | MR | Zbl

[12] Kolmogorov A. N., Tikhomirov V. M., “$\varepsilon$-entropy and $\varepsilon$-capacity of sets in function spaces”, American Mathematical Society Translations: Series 2, 17 (1961), 227–364 | MR | MR | Zbl

[13] Brusov V. S., Piyavskii S. A., “A computational algorithm for optimally covering a plane region”, USSR Computational Mathematics and Mathematical Physics, 11:2 (1971), 17–27 | DOI

[14] Piyavskii S. A., “On optimization of networks”, Izv. Akad. Nauk SSSR, Tekh. Kibern., 1968, no. 1, 68–80 (in Russian)

[15] Galiev Sh. I., Karpova M. A., “Optimization of multiple covering of a bounded set with circles”, Computational Mathematics and Mathematical Physics, 50:4 (2010), 721–732 | DOI | MR | Zbl

[16] Lebedev P. D., Uspenskii A. A., Ushakov V. N., “Algorithms of the best approximations of the flat sets by the union of circles”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 4, 88–99 (in Russian) | Zbl

[17] Bezdek K., Classical topics in discrete geometry, Springer, New York, 2010 | MR | Zbl

[18] Melissen H., “Densest packings of eleven congruent circles in a circle”, Geometriae Dedicata, 50:1 (1994), 15–25 | DOI | MR | Zbl

[19] Hausdorff F., Set theory, Komkniga, M., 2006, 304 pp.

[20] Garkavi A. L., “On the Chebyshev center and convex hull of a set”, Usp. Mat. Nauk, 19:6 (1964), 139–145 | MR | Zbl

[21] Ushakov V. N., Lebedev P. D., “Algorithms for the construction of an optimal cover for sets in three-dimensional Euclidean space”, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 21, no. 2, 2015, 276–288 (in Russian) | DOI | MR

[22] Tot L. F., Dispositions in a plane, on a sphere and in space, Gos. Izd. Fiz. Mat. Lit., M., 1958, 365 pp.

[23] Lebedev P. D., Ushakov A. V., “Approximating sets on a plane with optimal sets of circles”, Automation and Remote Control, 73:3 (2012), 485–493 | DOI | MR | Zbl

[24] Rashevskii P. K., Course of differential geometry, Editorial URSS, M., 2003, 432 pp.

[25] Akhiezer N. I., Elements of elliptic functions theory, Nauka, M., 1970, 304 pp. | MR

[26] Krotov V. F., Piyavskii S. A., “Sufficient conditions of optimality in problems of optimal covering”, Izv. Akad. Nauk SSSR, Tekh. Kibern., 1968, no. 2, 10–17 (in Russian) | MR