Multiple coverings of a closed set on a plane with non-Euclidean metrics by circles of two types
Các tác giả
Từ khóa:
bao phủ nhiều lần, các đường tròn khác nhau, phi Euclid, biểu đồ Voronoi, phương pháp quang-hình họcTóm tắt
The article is devoted to multiple covering problems for a closed set in a two-dimensional metric space by circles of two types. The number of circles of each class is given as well as a ratio of radii. This problem is as interesting and important as the classical circle covering problems. It is usually studied in the case when the distance between two points is Euclidean. We assume that the distance is determined using some particular metric arising in logistics, which, generally speaking, is not Euclidean. To solve this problem, we propose a computational algorithm based on a combination of the optical-geometric approach due to Fermat and Huygens principles and the Voronoi diagram. A key feature of the algorithm is the ability to deal with non-Euclidean metrics.
Abstract
The article is devoted to multiple covering problems for a closed set in a two-dimensional metric space by circles of two types. The number of circles of each class is given as well as a ratio of radii. This problem is as interesting and important as the classical circle covering problems. It is usually studied in the case when the distance between two points is Euclidean. We assume that the distance is determined using some particular metric arising in logistics, which, generally speaking, is not Euclidean. To solve this problem, we propose a computational algorithm based on a combination of the optical-geometric approach due to Fermat and Huygens principles and the Voronoi diagram. A key feature of the algorithm is the ability to deal with non-Euclidean metrics.
Tài liệu tham khảo
[1] B. B´anhelyi, E. Palatinus, B. L´evai, “Optimal circle covering problems and their applications”, Cent. Eur. J. Operat. Res, 23(4), 815-832, 2015.
[2] V. Brusov, S. Piyavskii, “A computational algorithm for optimally covering a plane region”, Comput. Math. Math. Phys., 11(2), 17-27, 1971.
[3] G. Das, S. Das, S. Nandy, B. Shina, “Efficient algorithm for placing a given number of base stations to cover a convex region”, J. Parallel Distrib. Comput, 66, 1353-1358, 2006.
[4] K. Al-Sultan, M. Hussain, J. Nizami, “A genetic algorithm for the set covering problem”, J. Operat. Res. Soc., 47(5), 702-709, 1996.
[5] S. Astrakov, A. Erzin, V. Zalyubovskiy, “Sensor networks and covering of plane by discs”, J. Appl. Indust. Math, 16(3), 3-19, 2009.
[6] M. Cardei, J. Wu, M. Lu, “Improving netwotk lifetime using sensors with adjustible sensing ranges”, Int. J. Sens. Netw, 1(1-2), 41- 49, 2006.
[7] D. Johnson, “Approximation algorithms for combinatorial problems”, J. Comput. System Sci., 9, 256-278,1974.
[8] G. Toth, “Thinnest covering of a circle by eight, nine, or ten congruent circles”, Comb. Comput. Geom., 52, 361-376, 2005.
[9] J. Zahn, “Black box maximization of circular coverage”, J. Res. Natl. Bur. Stand., 66, 181-216, 1962.
[10] L.F.Toth, “Solid circle-packings and circle-coverings”, Studia Sci. Math. Hungar, 3, 401-409, 1968.
[11] G.Toth, “Covering the plane with two kinds of circles”, Discret. Comput. Geom., 13, 445-457, 1995.
[12] A. Florian, A. Heppes, “Solid coverings of the euclidean plane with incongruent circles”, Discret. Comput. Geom, 23(2), 225-245, 2000.
[13] D. Dorninger, “Thinnest covering of the euclidean plane with incongruent circles”, Anal. Geom. Metr. Spaces, 5(1), 40-46, 2017.
[14] W. Blundon, “Multiple covering of the plane by circles”, Mathematika, 4, 7-16, 1957.
[15] S. Galiev, A. Khorkov, “Multiple circle coverings of an equilateral triangle, square, and circle”, Diskret. Anal. Issled. Oper., 22, 5-28, 2015.
[16] K. Sriamorn, “Multiple lattice packings and coverings of the plane with triangles”, Discrete Comput. Geom., 55, 228-242, 2016.
[17] C. Zong, “Packing, covering and tiling in two-dimension spaces”. Expo. Math., 32, 297- 364, 2012.
[18] V. Chvatal, “A greedy heuristic for the set covering”, Math. Optim. Res., 4, 233-235,1979.
[19] S. Ceria, P.Nobili, A. Sassano,“A lagrangian-based heuristic for large scale set covering problems”, Math. Progr, 81, 215-228, 1998.
[20] N. Hall, D. Hochbaum, “A fast appro-ximation algorithm for the multicovering problem”, Discret. Appl. Math., 15, 35-40, 1989.
[21] T. Fujito, “On combinatorial approximation of covering 0-1 integer programs and partial set cover. J”. Comb. Optim, 8, 439-452, 2004.
[22] A. Kazakov, A. Lempert, “An approach to optimization in transport logistics”, Autom. Remote Control, 72(7), 1398-1404, 2011.
[23] A. Kazakov, A. Lempert, “On mathematical models for optimization problem of logistics infrastructure”. Int. J. Artif. Intell.,13(1), 200-210, 2015.
[24] A. Kazakov, A. Lempert, M. Q. Le, “An algorithm for packing circles of two types in a fixed size container with non-euclidean metric”. In: Suppl. Proc. 6 Int. Conf. AIST, vol. 1975, pp. 281-292, 2017.
[25] S. Galiev, M. Karpova, “Optimization of multiple covering of a bounded set with circles”, Comput. Math. Math. Phys., 50, 721-732, 2010.
[26] A. Jain, R. Dubes, Algorithms for clustering data. New Jersy: Prentice Hall (1988).
[27] G.Toth, “Multiple packing and covering of the plane with circles”, Acta Math. Acad. Sci. Hungar., 27, 135-140, 1976.
[28] Z. Drezner, Facility location: A survey of applications and methods. Springer-Verl, New York, 1995.
[29] T. Tabirca, L. Yang, S. Tabirca “The smallest number of sensors for k-covering”, Int. J. Comput. Commun. Control, 8(2), 312-319, 2013.
[30] I. Bychkov, A. Kazakov, A. Lempert, D. Bukharov, A. Stolbov, “An intelligent ma-nagement system for the development of a regional transport logistics infrastructure”, Autom. Remote Control, 77(2), 332-343, 2016.
[31] A. Lempert, A. Kazakov, D. Bukharov, “Mathematical model and program system for solving a problem of logistic objects placement”, Autom. Remote Control, 76(8), 1463-1470, 2015.
[32] A. Lempert, M. Q. Le,“Multiple covering of a closed set on a plane with non-euclidean metrics”, IFAC-PapersOnLine, 51(32), 850-854, 2018.
[33] A. Borovskikh, “The two-dimensional eikonal equation”, Sib. Math. J., 47(2), 813- 834. 2006.
Tải xuống
Tải xuống: 13
