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.
Citation:
V. N. Ushakov, P. D. Lebedev, “Algorithms of optimal set covering on the planar R2”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 26:2 (2016), 258–270
\Bibitem{UshLeb16}
\by V.~N.~Ushakov, P.~D.~Lebedev
\paper Algorithms of optimal set covering on the planar $\mathbb{R}^2 $
\jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki
\yr 2016
\vol 26
\issue 2
\pages 258--270
\mathnet{http://mi.mathnet.ru/vuu537}
\crossref{https://doi.org/10.20537/vm160212}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3522930}
\elib{https://elibrary.ru/item.asp?id=26244785}
Linking options:
https://www.mathnet.ru/eng/vuu537
https://www.mathnet.ru/eng/vuu/v26/i2/p258
This publication is cited in the following 6 articles:
P. D. Lebedev, O. A. Kuvshinov, “Algoritmy postroeniya suboptimalnykh pokrytii ploskikh figur krugami v klassakh regulyarnykh reshetok”, Izv. IMI UdGU, 61 (2023), 76–93
S. N. Smirnov, “Guaranteed Deterministic Approach to Superhedging: Sensitivity of Solutions of the Bellman-Isaacs Equations and Numerical Methods”, Comput Math Model, 31:3 (2020), 384
P. D. Lebedev, “Iteratsionnye metody postroeniya approksimatsii optimalnykh pokrytii nevypuklykh ploskikh mnozhestv”, Chelyab. fiz.-matem. zhurn., 4:1 (2019), 5–17
Pavel Lebedev, Vladimir Ushakov, Communications in Computer and Information Science, 1090, Mathematical Optimization Theory and Operations Research, 2019, 244
P. D. Lebedev, N. G. Lavrov, “Algoritmy postroeniya optimalnykh upakovok sharov v ellipsoidy”, Izv. IMI UdGU, 52 (2018), 59–74
V. N. Ushakov, P. D. Lebedev, “Iteratsionnye metody minimizatsii khausdorfova rasstoyaniya mezhdu podvizhnymi mnogougolnikami”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 27:1 (2017), 86–97
Citation in format AMSBIB
Contact us: