ENRU  
Volume 22, No 6, 2015, P. 5–28 UDC 519.7
Keywords: multiple covering with congruent circles, equilateral trian gle, square, circle, minimum covering problem. DOI: 10.17377/daio.2015.22.482 Shamil I. Galiev ^{1} Received 17 March 2015 References[1] T. A. Aldynool, A. I. Erzin, and V. V. Zalyubovskiy, The coverage of a planar region by randomly deployed sensors, Vestn. NGU, Ser. Mat. Mekh. Inform., 10, No. 4, 7–25, 2010.[2] S. N. Astrakov, A. I. Erzin, and V. V. Zalyubovskiy, Sensor networks and covering of plane by discs, Diskretn. Anal. Issled. Oper., 16, No. 3, 3–19, 2009. [3] S. N. Astrakov and A. I. Erzin, Construction of efficient covering models in the monitoring of extended objects, Vychisl. Tekhnol., 17, No. 1, 26–34, 2012. [4] V. S. Brusov and S. A. Piyavskii, A computational algorithm for optimally covering a plane region, Zh. Vychisl. Mat. Mat. Fiz., 11, No. 2, 304–312, 1971. Translated in USSR Comput. Math. Math. Phys., 11, No. 2, 17–27, 1971. [5] Sh. I. Galiev, The directions of decrease for minmaxmin problems, Zh. Vychisl. Mat. Mat. Fiz., 34, No. 3, 323–343, 1994. Translated in Comput. Math. Math. Phys., 34, No. 3, 271–286, 1994. [6] Sh. I. Galiev and V. I. Zabotin, On continuous surveys of Earth’s surface, Issled. Zemli Kosm., No. 1, 117–120, 1983. [7] Sh. I. Galiev and M. A. Karpova, Optimization of multiple covering of a bounded set with circles, Zh. Vychisl. Mat. Mat. Fiz., 50, No. 4, 757–769, 2010. Translated in Comput. Math. Math. Phys., 50, No. 4, 721–732, 2010. [8] Sh. I. Galiev and M. A. Karpova, Multiple coverings of a square with circles. I, Vestn. KGTU Tupoleva, No. 1, 86–93, 2013. [9] Sh. I. Galiev and M. A. Karpova, Multiple coverings of a square with circles. II, Vestn. KGTU Tupoleva, No. 21, 88–92, 2013. [10] Sh. I. Galiev and A. V. Khorkov, Some extreme multiple coverings a square with circles, Vestn. KGTU Tupoleva, No. 2, 154–159, 2014. [11] A. V. Eremeev, L. A. Zaozerskaya, and A. A. Kolokolov, The set covering problem: Complexity, algorithms, and experimental investigations, Diskretn. Anal. Issled. Oper., Ser. 2, 7, No. 2, 22–46, 2000. [12] N. N. Kuzyurin, On the complexity of asymptotically optimal coverings and packing, Dokl. Akad. Nauk, 363, No. 1, 11–13, 1998. Translated in Dokl. Math., 58, No. 3, 345–346, 1998. [13] G. V. Mozhaev, Problem of continuous survey of Earth’s surface and kinematic regular satellite systems, Kosm. Issled., 10, No. 6, 833–840, 1972. [14] I. I. Takhonov, On some problems of covering the plane with circles, Diskretn. Anal. Issled. Oper., 21, No. 1, 84–102, 2014. [15] M. Yu. Khachai and M. I. Poberii, Computational complexity and approximability of a series of geometric covering problems, Tr. Inst. Mat. Mekh., 18, No. 3, 247–260, 2012. Translated in Proc. Steklov Inst. Math., 284, Suppl. 1, S87–S95, 2014. [16] V. V. Shenmaier, The smallest kenclosing ball problem, Diskretn. Anal. Issled. Oper., 20, No. 1, 93–99, 2013. [17] H. M. Ammari, Challenges and Opportunities of Connected kCovered Wireless Sensor Networks: From Sensor Deployment to Data Gathering, Springer, Heidelberg, 2009 (Stud. Comput. Intell., Vol. 215). [18] D. Bertsimas and R. Vohra, Rounding algorithms for covering problems, Math. Program., Ser. A, 80, No. 1, 63–89, 1998. [19] K. Bezdek, Über einige Kreisüberdeckungen, Beitr. Algebra Geom., 14, 7–13, 1983 [German]. [20] J. Brimberg and Z. Drezner, A new heuristic for solving the pmedian problem in the plane, Comput. Oper. Res., 40, No. 1, 427–437, 2013. [21] V. Chvatal, A greedy heuristic for the setcovering problem, Math. Oper. Res., 4, No. 1, 233–235, 1979. [22] Z. Drezner, ed., Facility Location: A Survey of Applications and Methods, Springer, New York, 1995 (Springer Ser. Oper. Res. Financ. Eng.). [23] A. I. Erzin and S. N. Astrakov, Mindensity stripe covering and applications in sensor networks, in Computational Science and Its Applications  ICCSA 2011 (Proc. 2011 Int. Conf. Comput. Sci. Its Appl., Santander, Spain, June 20–23, 2011), Pt. III, pp. 152–162, Springer, Heidelberg, 2011 (Lect. Notes Comput. Sci., Vol. 6784). [24] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982. [25] N. G. Hall and D. S. Hochbaum, A fast approximation algorithm for the multicovering problem, Discrete Appl. Math., 15, No. 1, 35–40, 1986. [26] M. Hefeeda and M. Bagheri, Randomized kcoverage algorithms for dense sensor networks, in Proc. 26th IEEE Int. Conf. Comput. Commun., Anchorage, AK, USA, May 6–12, 2007, pp. 2376–2380, IEEE, Piscataway, 2007. [27] A. Kononov, S. Sevastianov, and M. Sviridenko, A ñomplete 4parametric complexity classification of short shop scheduling problems, J. Scheduling, 15, 427–446, 2012. [28] S. Krotoszy´nski, Covering a disk with smaller disks, Stud. Sci. Math. Hung., 28, No. 3–4, 277–283, 1993. [29] N. Megiddo and K. J. Supowit, On the complexity of some common geometric location problems, SIAM J. Comput., 13, No. 1, 182–196, 1984. [30] H. Melissen, Loosest circle coverings of an equilateral triangle, Math. Mag., 70, No. 2, 118–124, 1997. [31] J. B. M. Melissen and P. C. Schuur, Improved coverings of a square with six and eight equal circles, Electron. J. Comb., 3, No. 1/R32, 1–10, 1996. [32] J. B. M. Melissen and P. C. Schuur, Covering a rectangle with six and seven circles, Discrete Appl. Math., 99, No. 1–3, 149–156, 2000. [33] K. J. Nurmela, Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles, Exp. Math., 9, No. 2, 241–250, 2000. [34] K. J. Nurmela and P. R. J. Östergård, Covering a square with up to 30 equal circles, Res. Rep. 62, Helsinki Univ. Technol., Helsinki, Finland, 2000. Available at http://www.tcs.hut.fi/old/reports/A62abstract.html. Accessed Oct. 20, 2015. [35] T. Tabirca, L. T. Yang, and S. Tabirca, Smallest number of sensors for kcovering, Int. J. Comput. Commun. Control, 8, No. 2, 312–319, 2013. [36] T. Tarnai and Zs. Gáspár, Covering a square by equal circles, Elem. Math., 50, 167–170, 1995. [37] G. F. Tóth, Packing and covering, in J. E. Goodman and J. O’Rourke, eds., Handbook of Discrete and Computational Geometry, pp. 19–41, CRC Press, Boca Raton, 1997. [38] G. F. Tóth, Thinnest covering of a circle by eight, nine, or ten congruent circles, in J. E. Goodman, J. Pach, and E. Welzl, eds., Combinatorial and Computational Geometry, pp. 361–376, Cambridge Univ. Press, New York, 2005 (Math. Sci. Res. Inst. Publ., Vol. 52). [39] S. Verblunsky, On the least number of unit circles which can cover a square, J. London Math. Soc., 24, No. 3, 164–170, 1949. 

© Sobolev Institute of Mathematics, 2015  