phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2013 - 4 issue » pp. 88-99

Archive of Issues

Russia Yekaterinburg
Year
2013
Issue
4
Pages
88-99
<<
>>
Section Mathematics
Title Algorithms of the best approximations of the flat sets by the union of circles
Author(-s) Lebedev P.D.a, Uspenskii A.A.a, Ushakov V.N.a
Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa
Abstract 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
UDC 514.174.3
MSC 05B40
DOI 10.20537/vm130409
Received 30 October 2013
Language Russian
Citation Lebedev P.D., Uspenskii A.A., Ushakov V.N. Algorithms of the best approximations of the flat sets by the union of circles, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, issue 4, pp. 88-99.
References
  1. Krasovskii N.N., Subbotin A.I. Pozitsionnye differentsial'nye igry (Positional differential games), Moscow: Nauka, 1974, 456 p.
  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, 2006, vol. 12, no. 2, pp. 178-194.
  3. Ushakov V.N., Uspenskii A.A. On a supplement to the stability property in differential games, Proceedings of the Steklov Institute of Mathematics, 2010, vol. 271, issue 1, pp. 286-305.
  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, 2011, vol. 17, no. 2, pp. 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, pp. 87-103.
  6. Lebedev P.D., Ushakov A.V. Approximating sets on a plane with optimal sets of circles, Automation and Remote Control, 2012, vol. 73, issue 3, pp. 79-90.
  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, pp. 72-87.
  8. Kurzhanski A.B., Valyi I. Ellipsoidal calculus for estimation and control, Boston: Birkhauser, 1997, 220 p.
  9. Gusev M.I. Estimates of reachable sets of multidimensional control systems with nonlinear interconnections, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 2009, vol. 15, no. 4, pp. 82-94.
  10. Garkavi A.L. Existence of the best net and the best width for set in a Banach space, Usp. Mat. Nauk, 1960, vol. 15, issue 2, pp. 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., 1962, vol. 26, no. 1, pp. 87-106.
  12. Garkavi A.L. On the Chebyshev center and convex hull of a set, Usp. Mat. Nauk, 1964, vol. 19, issue 6, pp. 139-145.
  13. Garkavi A.L. Method of cyclic descent in the problem of best approximation, Mat. Zametki, 1980, vol. 27, no. 4, pp. 549-558.
  14. Sosov E.N. On approximation properties of sets in special metric spaces, Izv. Vyssh. Uchebn. Zaved., Mat., 1999, no. 6, pp. 81-84.
  15. Sosov E.N. Vvedenie v metricheskuyu geometriyu. Chast' 2 (Introduction to metric geometry. Part 2), Kazan: Kazan State University, 2008, 29 p.
  16. Sosov E.N. Metric space of all N-nets of a geodesic space, Uch. Zap. Kazan. Gos. Univ., Ser. Fiz.-Mat. Nauki, 2009, vol. 151, no. 4, pp. 136-149.
  17. Hausdorff F. Teoriya mnozhestv (Set theory), Moscow: Komkniga, 2006, 304 p.
  18. Yaglom I.M., Boltyanskii V.G. Vypuklye figury (Convex figures), Moscow-Leningrad: Gostekhteorizdat, 1951, 343 p.
  19. Piyavskii S.A. On optimization of nets, Izv. Akad. Nauk SSSR, Tekh. Kibern., 1968, no. 1, pp. 68-80.
  20. Brusov V.S., Piyavskii S.A. A computational algorithm for optimally covering a plane region, Zh. Vychisl. Mat. Mat. Fiz., 1971, vol. 11, no. 2, pp. 304-312.
  21. Galiev Sh.I., Karpova M.A. Optimization of a multiple covering of a bounded set with circles, Zh. Vychisl. Mat. Mat. Fiz., 2010, vol. 50, no. 4, pp. 757-769.
  22. Preparata F., Shamos M. Computational geometry, New York-Berlin-Heidelberg: Springer-Verlag, 1985. Translated under the title Vychislitel'naya geometriya, Moscow: Mir, 1989, 478 p.
Full text
/doc/issues-2013/13-04-09.pdf
<< Previous article
Next article >>