phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2016 - 2 issue » pp. 258-270

Archive of Issues

Russia Yekaterinburg
Year
2016
Volume
26
Issue
2
Pages
258-270
<<
>>
Section Mathematics
Title Algorithms of optimal set covering on the planar $\mathbb{R}^2$
Author(-s) Ushakov V.N.a, Lebedev P.D.a
Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa
Abstract 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
UDC 514.174.3
MSC 05B40
DOI 10.20537/vm160212
Received 15 April 2016
Language Russian
Citation Ushakov V.N., Lebedev P.D. Algorithms of optimal set covering on the planar $\mathbb{R}^2$, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2016, vol. 26, issue 2, pp. 258-270.
References
  1. Krasovskii N.N., Subbotin A.I. Pozitsionnye differentsial'nye igry (Positional differential games), Мoscow: Nauka, 1974, 456 p.
  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, 2012, vol. 277, issue 1, pp. 266-277.
  3. Mestetskii L.M. Nepreryvnaya morfologiya binarnykh izobrazhenii: figury, skelety, tsirkulyary (Continuous morphology of binary images: figures, skeletons, circulars), Moscow: Fizmatlit, 2009, 288 p.
  4. Kurzhanskii A.B., Filippova T.F. Description of the set of viable trajectories of a differential inclusion, Dokl. Akad. Nauk SSSR, 1986, vol. 289, no. 1, pp. 38-41 (in Russian).
  5. Chernous'ko F.L. Otsenivanie fazovogo sostoyaniya dinamicheskikh sistem (Evaluation of a phase state of dynamical systems), Moscow: Nauka, 1988, 384 p.
  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, pp. 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, 2014, vol. 20, no. 4, pp. 277-286 (in Russian).
  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, 2015, vol. 291, suppl. 1, pp. 222-238.
  9. 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 (in Russian).
  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., 1962, vol. 26, no. 1, pp. 87-106 (in Russian).
  11. Kolmogorov A.N. On some asymptotic characteristics of completely bounded metric spaces, Dokl. Akad. Nauk SSSR, 1956, vol. 108, no. 3, pp. 385-388 (in Russian).
  12. Kolmogorov A.N., Tikhomirov V.M. $\varepsilon$-entropy and $\varepsilon$-capacity of sets in function spaces, American Mathematical Society Translations: Series 2, 1961, vol. 17, pp. 227-364.
  13. Brusov V.S., Piyavskii S.A. A computational algorithm for optimally covering a plane region, USSR Computational Mathematics and Mathematical Physics, 1971, vol. 11, issue 2, pp. 17-27.
  14. Piyavskii S.A. On optimization of networks, Izv. Akad. Nauk SSSR, Tekh. Kibern., 1968, no. 1, pp. 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, 2010, vol. 50, issue 4, pp. 721-732.
  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, pp. 88-99 (in Russian).
  17. Bezdek K. Classical topics in discrete geometry, New York: Springer, 2010.
  18. Melissen H. Densest packings of eleven congruent circles in a circle, Geometriae Dedicata, 1994, vol. 50, issue 1, pp. 15-25.
  19. Hausdorff F. Teoriya mnozhestv (Set theory), Moscow: Komkniga, 2006, 304 p.
  20. Garkavi A.L. On the Chebyshev center and convex hull of a set, Usp. Mat. Nauk, 1964, vol. 19, issue 6, pp. 139-145.
  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, 2015, vol. 21, no. 2, pp. 276-288 (in Russian).
  22. Tot L.F. Raspolozheniya na ploskosti, na sfere i v prostranstve (Dispositions in a plane, on a sphere and in space), Moscow: Gos. Izd. Fiz. Mat. Lit., 1958, 365 p.
  23. 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. 485-493.
  24. Rashevskii P.K. Kurs differentsial'noi geometrii (Course of differential geometry), Moscow: Editorial URSS, 2003, 432 p.
  25. Akhiezer N.I. Elementy teorii ellipticheskikh funktsii (Elements of elliptic functions theory), Moscow: Nauka, 1970, 304 p.
  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, pp. 10-17 (in Russian).
Full text
/doc/issues-2016/16-02-12.pdf
<< Previous article
Next article >>