Volume 22, No 6, 2015, P. 5–28
UDC 519.7
Sh. I. Galiev and A. V. Khorkov
Multiple circle coverings of an equilateral triangle, square, and circle
Abstract:
We study k-fold coverings of an equilateral triangle, square, and circle with n congruent circles of the minimum possible radius r*n,k. We describe mathematical models for these problems and algorithms for their solving. We also prove optimality of the constructed coverings for certain n and k, 1 < k ≤ n. For n ≤ 15 and 1 < k ≤ n, we present the best found (possibly, improvable) values of circles radii ensuring the k-fold covering of the equilateral triangle, square or a circle.
Ill. 4, tab. 3, bibliogr. 39.
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
Alexander V. Khorkov 1
1. Kazan National Research Technological University,
10 K. Marx St., 420011 Kazan, Russia
e-mail: sh.galiev@mail.ru, aLex22fcrk@yandex.ru
Received 17 March 2015
Revised 20 August 2015
References
[1] T. A. Aldyn-ool, 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. 2-1, 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 k-enclosing ball problem, Diskretn. Anal. Issled. Oper., 20, No. 1, 93–99, 2013.
[17] H. M. Ammari, Challenges and Opportunities of Connected k-Covered 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 p-median problem in the plane, Comput. Oper. Res., 40, No. 1, 427–437, 2013.
[21] V. Chvatal, A greedy heuristic for the set-covering 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, Min-density 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 NP-Completeness, 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 k-coverage 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 4-parametric 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 k-covering, 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.
