Geodesic
Algorithms of the best approximations of the flat sets by the union of circles
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 4 (2013), pp. 88-99 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The article is devoted to the problem of constructing an optimal approximating circle-cover for the bounded flat set by the finite number of circles with equal radius. The problem is solved if the best $n$-net in meaning of Hausdorff metric is constructed for the considered set. Sufficient conditions of optimality of the $n$-nets are given. The best net-construction algorithm based on dividing of the set $M$ into subsets and finding their Chebyshev centers is realized. This algorithm is proved to be efficient with the examples of sets with different geometry.
Keywords: Chebyshev center, the best net, circle cover. 
@article{VUU_2013_4_a8,
     author = {P. D. Lebedev and A. A. Uspenskii and V. N. Ushakov},
     title = {Algorithms of the best approximations of the flat sets by the union of circles},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {88--99},
     year = {2013},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2013_4_a8/}
}
TY  - JOUR
AU  - P. D. Lebedev
AU  - A. A. Uspenskii
AU  - V. N. Ushakov
TI  - Algorithms of the best approximations of the flat sets by the union of circles
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2013
SP  - 88
EP  - 99
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VUU_2013_4_a8/
LA  - ru
ID  - VUU_2013_4_a8
ER  - 
%0 Journal Article
%A P. D. Lebedev
%A A. A. Uspenskii
%A V. N. Ushakov
%T Algorithms of the best approximations of the flat sets by the union of circles
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2013
%P 88-99
%N 4
%U http://geodesic.mathdoc.fr/item/VUU_2013_4_a8/
%G ru
%F VUU_2013_4_a8
P. D. Lebedev; A. A. Uspenskii; V. N. Ushakov. Algorithms of the best approximations of the flat sets by the union of circles. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 4 (2013), pp. 88-99. http://geodesic.mathdoc.fr/item/VUU_2013_4_a8/

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

[2] Ushakov V. N., Latushkin Ya. A., “The stability defect of sets in game control problems”, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 12, no. 2, 2006, 178–194 | MR | Zbl

[3] Ushakov V. N., Uspenskii A. A., “On a supplement to the stability property in differential games”, Proceedings of the Steklov Institute of Mathematics, 271, no. 1, 2010, 286–305 | DOI | MR

[4] Ushakov V. N., Uspenskii A. A., Malev A. G., “Estimate of the stability defect for a positional absorption set subjected to discriminant transformations”, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 17, no. 2, 2011, 209–224

[5] 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

[6] 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

[7] Lebedev P. D., Bukharov D. S., “Approximation of polygons with the best set of circles”, Izvestiya Irkutskogo Gosudarstvennogo Universiteta. Seriya Matematika, 2013, no. 3, 72–87 | Zbl

[8] Kurzhanski A. B., Valyi I., Ellipsoidal calculus for estimation and control, Birkhauser, Boston, 1997, 220 pp. | MR | Zbl

[9] Gusev M. I., “Estimates of reachable sets of multidimensional control systems with nonlinear interconnections”, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 15, no. 4, 2009, 82–94

[10] 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

[11] 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 | MR | Zbl

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

[13] Garkavi A. L., “Method of cyclic descent in the problem of best approximation”, Mat. Zametki, 27:4 (1980), 549–558 | MR | Zbl

[14] Sosov E. N., “On approximation properties of sets in special metric spaces”, Izv. Vyssh. Uchebn. Zaved., Mat., 1999, no. 6, 81–84 | MR | Zbl

[15] Sosov E. N., Introduction to metric geometry, Part 2, Kazan State University, Kazan, 2008, 29 pp.

[16] Sosov E. N., “Metric space of all $N$-nets of a geodesic space”, Uch. Zap. Kazan. Gos. Univ., Ser. Fiz.-Mat. Nauki, 151, no. 4, 2009, 136–149 | Zbl

[17] Hausdorff F., Set theory, Komkniga, Moscow, 2006, 304 pp.

[18] Yaglom I. M., Boltyanskii V. G., Convex figures, Gostekhteorizdat, Moscow–Leningrad, 1951, 343 pp. | MR

[19] Piyavskii S. A., “On optimization of nets”, Izv. Akad. Nauk SSSR, Tekh. Kibern., 1968, no. 1, 68–80

[20] Brusov V. S., Piyavskii S. A., “A computational algorithm for optimally covering a plane region”, Zh. Vychisl. Mat. Mat. Fiz., 11:2 (1971), 304–312 | Zbl

[21] Galiev Sh. I., Karpova M. A., “Optimization of a multiple covering of a bounded set with circles”, Zh. Vychisl. Mat. Mat. Fiz., 50:4 (2010), 757–769 | MR | Zbl

[22] Preparata F., Shamos M., Computational geometry, Springer-Verlag, New York–Berlin–Heidelberg, 1985 | MR | MR | Zbl | Zbl