Algorithms for constructing suboptimal coverings of plane figures with disks in the class of regular lattices

P. D. Lebedev ; O. A. Kuvshinov

Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 61 (2023), pp. 76-93.

Résumé

The problem of covering a compact planar set $M$ with a set of congruent disks is considered. It is assumed that the centers of the circles belong to some lattice. The criterion of optimality in one case is the minimum of the number of elements of the covering, and in the other case — the minimum of the Hausdorff deviation of the union of elements of the covering from the set $M$. To solve the problems, transformations of parallel transfer and rotation with the center at the origin can be applied to the lattice. Statements concerning sufficient conditions for sets of circles that provide solutions to the problems are proved. Numerical algorithms based on minimizing the Hausdorff deviation between two flat compacts are proposed. Solutions of a number of examples are given for various figures of $M$.

Détail

Keywords: covering, circle, Hausdorff deviation, minimization.
Mots-clés : Bravais lattice

Bibliographie

[1] Krasovskii N.N., Some problems of the theory of stability of motion, Fizmatgiz, Moscow, 1959

[2] Krasovskii N.N., Subbotin A.I., Positional differential games, Fizmatlit, Moscow, 1974 | MR

[3] Kazakov A.L., Lempert A.A., Bukharov D.S., “On segmenting logistical zones for servicing continuously developed consumers”, Automation and Remote Control, 74:6 (2013), 968–977 | DOI | MR | Zbl

[4] Conway J.H., Sloane N.J.A., Sphere packings, lattices and groups, Springer, New York, 1988 | DOI | MR | MR | Zbl

[5] Tóth L.F., Lagerungen in der Ebene auf der Kugel und im Raum, Springer-Verlag, Berlin, 1953 https://archive.org/details/lagerungenindere0000feje | MR | Zbl

[6] 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, 26:2 (2016), 258–270 (in Russian) | DOI | MR | Zbl

[7] Lebedev P.D., Lempert A.A., Kazakov A.L., “Algorithms of optimal covering of 2D sets with dynamical metrics”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 60 (2022), 58–72 (in Russian) | DOI | MR | Zbl

[8] Ushakov V.N., Lebedev P.D., Lavrov N.G., “Algorithms of optimal packing construction in ellipse”, Vestnik Yuzhno-Ural'skogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie, 10:3 (2017), 67–79 (in Russian) | DOI | Zbl

[9] Dorninger D., “Thinnest covering of the Euclidean plane with incongruent circles”, Analysis and Geometry in Metric Spaces, 5:1 (2017), 40–46 | DOI | MR | Zbl

[10] Prosanov R., “On a relation between packing and covering densities of convex bodies”, Discrete and Computational Geometry, 65:4 (2021), 1028–1037 | DOI | MR | Zbl

[11] Bánhelyi B., Palatinus E, Lévai B.L., “Optimal circle covering problems and their applications”, Central European Journal of Operations Research, 23:4 (2015), 815–832 | DOI | MR

[12] Nasab H.H., Tavana M., Yousefi M., “A new heuristic algorithm for the planar minimum covering circle problem”, Production and Manufacturing Research, 2:1 (2014), 142–155 | DOI

[13] Birgin E.G., Gómez W., Haeser G., Mito L.M., Santos D.O., “An augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem”, Computational and Applied Mathematics, 39:1 (2020), 10 | DOI | MR | Zbl

[14] Birgin E.G., Laurain A., Massambone R., Santana A.G., “A shape optimization approach to the problem of covering a two-dimensional region with minimum-radius identical balls”, SIAM Journal on Scientific Computing, 43:3 (2021), A2047–A2078 | DOI | MR | Zbl

[15] Zong Chuanming, “Packing, covering and tiling in two-dimensional spaces”, Expositiones Mathematicae, 32:4 (2014), 297–364 | DOI | MR | Zbl

[16] Klyuev L., [Electronic resource] (in Russian) (29.01.2023) https://habr.com/ru/company/yandex/blog/522900/

[17] Sukharev A.G., Timokhov A.V., Fedorov V.V., Optimization methods: textbook and workshop for undergraduate and graduate students, Yurait, Moscow, 2014

[18] 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, 291, suppl. 1 (2015), 222–238 | DOI | MR

[19] Danilov D.I., Lakhtin A.S., “Optimization of the algorithm for determining the Hausdorff distance for convex polygons”, Ural Mathematical Journal, 4:1 (2018), 14–23 | DOI | MR | Zbl

[20] Garkavi A.L., “On the Chebyshev center and convex hull of a set”, Uspekhi Matematicheskikh Nauk, 19:6(120) (1964), 139–145 (in Russian) | MR | Zbl

[21] Chen Ke, Giblin P.J., Irving A., Mathematical explorations with MATLAB, Cambridge University Press, Cambridge, 1999 https://archive.org/details/mathematicalexpl0000chen

[22] Kuvshinov O.A., “About the geometry of the Cassini oval, its non-convexity degree and $\varepsilon$-offset layer”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 60 (2022), 34–57 (in Russian) | DOI | MR | Zbl

[23] Glazyrin A., “Covering a ball by smaller balls”, Discrete and Computational Geometry, 62:4 (2019), 781–787 | DOI | MR | Zbl