Construction of optimal covers by disks of different radii for convex planar sets

P. D. Lebedev   ; A. L. Kazakov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 2, pp. 137-148

Résumé

We consider the problem of constructing an optimal cover of a planar set $M$ by the union of a given number of disks. In the general case, the radii of the disks are assumed to be different; each radius is the product of some positive factor specific for each disk and a parameter $r$, which is common for all elements of the cover. The optimality criterion is the minimum of $r$ under the condition that $M$ is a subset of the union of the disks. For a set of points $S$, we write the value of $r$ that defines the minimum radius of the disks centered at the points of $S$ and implementing a cover of $M$. Expressions are found that analytically describe the impact zones (the so-called generalized Dirichlet zones) of the points of $S$, which differ significantly from the expressions for the case of congruent circles. A procedure for the iterative correction of coordinates of $S$ based on finding Chebyshev centers of impact zones of points is proposed. It is shown that the procedure does not degrade the properties of the cover, while its parameters can be changed in the process of starting the software complex. Numerical experiments on the construction of optimal covers by families of disks were carried out with different coefficients defining the radii of the disks. Various convex polygons were taken as the set $M$, and the results were visualized.

Détail

Keywords: optimal cover, generalized Dirichlet zone, Chebyshev center, iterative algorithm, minimization.

Bibliographie

[1] Lempert A.A., Kazakov A.L., Bukharov D.S., “Mathematical model and program system for solving a problem of logistic objects placement”, Autom. Remote Control, 76:8 (2015), 1463–1470 | DOI | Zbl

[2] Bychkov I.V., Kazakov A.L., Lempert A.A., Bukharov D.S., Stolbov A.B., “An intelligent management system for the development of a regional transport logistics infrastructure”, Autom. Remote Control, 77:2 (2016), 332–343 | DOI | MR | Zbl

[3] Preparata F.P., Shamos M.I., Computational geometry: An introduction, Springer-Verlag, N Y, 1985, 398 pp. | DOI | MR

[4] Tot L.F., Raspolozheniya na ploskosti, na sfere i v prostranstve, Fizmatlit, Moskva, 1958, 364 pp.

[5] Kazakov A.L., Lebedev P.D., “Algoritmy postroeniya nailuchshikh $n$-setei v metricheskikh prostranstvakh”, Avtomatika i telemekhanika, 2017, no. 7, 141–155 | DOI | Zbl

[6] Lempert, A., Le, Q.M., “Multiple covering of a closed set on a plane with non-Euclidean metrics”, IFAC-PapersOnLine, 51:32 (2018), 850–854 | DOI

[7] Toth L.F., “Solid circle-packings and circle-coverings”, Studia Sci. Math. Hungar, 3 (1968), 401–409 | MR | Zbl

[8] Toth F. G., “Covering the plane with two kinds of circles”, Discrete Comput. Geom., 13:3-4 (1995), 445–457 | DOI | MR | Zbl

[9] Florian A., Heppes A., “Solid coverings of the Euclidean plane with incongruent circles”, Discrete Comput. Geom., 23:2 (2000), 225–245 | DOI | MR | Zbl

[10] Dorninger D., “Thinnest covering of the Euclidean plane with incongruent circles”, Anal. Geom. Metr. Spaces, 5:1 (2017), 40–46 | DOI | MR | Zbl

[11] Banhelyi B., Palatinus E, Levai B.L., “Optimal circle covering problems and their applications”, Central Europ. J. Oper. Research, 23:4 (2015), 815–832 | DOI | MR | Zbl

[12] Kazakov A.L., Lempert A.A., Le Q.M., “An algorithm for packing circles of two types in a fixed size container with non-Euclidean metric”, CEUR-WS, 1975 (2017), 286–297

[13] Kazakov A., Lempert A., Lebedev P., “Congruent circles packing and covering problems for multi-connected domains with non-euclidean metric, and their applications to logistics”, CEUR-WS, 1839 (2017), 334–343

[14] Lempert A., Kazakov A., Le Q.M., “On reserve and double covering problems for the sets with non-Euclidean metrics”, Yugoslav J. Oper. Research, 29:1 (2019), 69–79 | DOI | MR

[15] Lebedev P.D., “Iteratsionnye metody postroeniya approksimatsii optimalnykh pokrytii nevypuklykh ploskikh mnozhestv”, Chelyab. fiz.-matem. zhurn., 4:1 (2019), 5–17 | DOI | MR

[16] Brusov V.S., Piyavskii S.A., “Vychislitelnyi algoritm optimalnogo pokrytiya oblastei ploskosti”, Zhurn. vychisl. matematiki i mat. fiziki, 11:2 (1971), 304–312

[17] Garkavi A.L., “O chebyshevskom tsentre i vypukloi obolochke mnozhestva”, Uspekhi mat. nauk, 19:6 (120) (1964), 139–145 | MR | Zbl

[18] Pshenichnyi B. N., Vypuklyi analiz i ekstremalnye zadachi, Nauka, M., 1980, 320 pp. | MR

[19] Lebedev P.D., Programma vychisleniya optimalnogo pokrytiya polusfery naborom sfericheskikh segmentov. Svidetelstvo o gosudarstvennoi registratsii No 2015661543 ot 29.10.2015