Geodesic
Multiple circle coverings of an equilateral triangle, square, and circle
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 6, pp. 5-28.

Voir la notice de l'article provenant de la source Math-Net.Ru

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$. For $n\le15$ and $1$, 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 triangle, square, circle, minimum covering problem. 
@article{DA_2015_22_6_a0,
     author = {Sh. I. Galiev and A. V. Khorkov},
     title = {Multiple circle coverings of an equilateral triangle, square, and circle},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--28},
     publisher = {mathdoc},
     volume = {22},
     number = {6},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_6_a0/}
}
TY  - JOUR
AU  - Sh. I. Galiev
AU  - A. V. Khorkov
TI  - Multiple circle coverings of an equilateral triangle, square, and circle
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 5
EP  - 28
VL  - 22
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_6_a0/
LA  - ru
ID  - DA_2015_22_6_a0
ER  - 
%0 Journal Article
%A Sh. I. Galiev
%A A. V. Khorkov
%T Multiple circle coverings of an equilateral triangle, square, and circle
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 5-28
%V 22
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_6_a0/
%G ru
%F DA_2015_22_6_a0
Sh. I. Galiev; A. V. Khorkov. Multiple circle coverings of an equilateral triangle, square, and circle. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 6, pp. 5-28. http://geodesic.mathdoc.fr/item/DA_2015_22_6_a0/

[1] T. A. Aldyn-ool, A. I. Erzin, V. V. Zalyubovskiy, “The coverage of a planar region by randomly deployed sensors”, Vestn. NGU, Ser. Mat. Mekh. Inform., 10:4 (2010), 7–25 | Zbl

[2] S. N. Astrakov, A. I. Erzin, V. V. Zalyubovskiy, “Sensor networks and covering of plane by discs”, Diskretn. Anal. Issled. Oper., 16:3 (2009), 3–19 | MR | Zbl

[3] S. N. Astrakov, A. I. Erzin, “Construction of efficient covering models in the monitoring of extended objects”, Vychisl. Tekhnol., 17:1 (2012), 26–34

[4] V. S. Brusov, S. A. Piyavskii, “A computational algorithm for optimally covering a plane region”, USSR Comput. Math. Math. Phys., 11:2 (1971), 17–27 | DOI | Zbl

[5] Sh. I. Galiev, “The directions of decrease for minmaxmin problems”, Comput. Math. Math. Phys., 34:3 (1994), 271–286 | MR | Zbl

[6] Sh. I. Galiev, V. I. Zabotin, “On continuous surveys of Earth's surface”, Issled. Zemli Kosm., 1983, no. 1, 117–120 | MR

[7] Sh. I. Galiev, M. A. Karpova, “Optimization of multiple covering of a bounded set with circles”, Comput. Math. Math. Phys., 50:4 (2010), 721–732 | MR | Zbl

[8] Sh. I. Galiev, M. A. Karpova, “Multiple circle coverings of a square. I”, Vestn. KGTU Tupoleva, 2013, no. 1, 86–93

[9] Sh. I. Galiev, M. A. Karpova, “Multiple circle coverings of a square. II”, Vestn. KGTU Tupoleva, 2013, no. 2-1, 88–92

[10] Sh. I. Galiev, A. V. Khorkov, “Some extreme multiple circle coverings of a square”, Vestn. KGTU Tupoleva, 2014, no. 2, 154–159

[11] A. V. Eremeev, L. A. Zaozerskaya, A. A. Kolokolov, “The set covering problem: Complexity, algorithms, and experimental investigations”, Diskretn. Anal. Issled. Oper., Ser. 2, 7:2 (2000), 22–46 | MR | Zbl

[12] N. N. Kuzyurin, “On the complexity of asymptotically optimal coverings and packing”, Dokl. Math., 58:3 (1998), 345–346 | MR | Zbl

[13] G. V. Mozhaev, “Problem of continuous survey of Earth's surface and kinematic regular satellite systems”, Kosm. Issled., 10:6 (1972), 833–840

[14] I. I. Takhonov, “On some problems of covering the plane with circles”, Diskretn. Anal. Issled. Oper., 21:1 (2014), 84–102 | MR | Zbl

[15] M. Yu. Khachai, M. I. Poberii, “Computational complexity and approximability of a series of geometric covering problems”, Proc. Steklov Inst. Math., 283, Suppl. 1, 2013, 64–77 | DOI

[16] V. V. Shenmaier, “The smallest $k$-enclosing ball problem”, Diskretn. Anal. Issled. Oper., 20:1 (2013), 93–99 | MR | Zbl

[17] Ammari H. M., Challenges and opportunities of connected $k$-covered wireless sensor networks, Springer-Verl., Berlin–Heidelberg, 2009, 342 pp. | MR | Zbl

[18] Bertsimas D., Vohra R., “Rounding algorithms for covering problems”, Math. Program. Ser. A, 80:1 (1998), 63–89 | DOI | MR | Zbl

[19] Bezdek K., “Über einige Kreisüberdeckungen”, Beitr. Algebra Geom., 14 (1983), 7–13 (German) | MR | Zbl

[20] Brimberg J., Drezner Z., “A new heuristic for solving the $p$-median problem in the plane”, Comput. Oper. Res., 40:1 (2013), 427–437 | DOI | MR

[21] Chvatal V., “A greedy heuristic for the set covering”, Math. Oper. Res., 4:1 (1979), 233–235 | DOI | MR | Zbl

[22] Drezner Z., Facility location: A survey of applications and methods, New York, Springer-Verl., 1995, 571 pp. | MR

[23] Erzin A. I., Astrakov S. N., “Min-density stripe covering and applications in sensor networks”, Proc. 2011 Int. Conf. Comput. Sci. Its Appl., Pt. III, Santander, Spain, June 20–23, 2011, 6784, Springer-Verl., Heidelberg, 2011, 152–162 | MR

[24] Garey M. R., Johnson D. S., Computers and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, 1979, 339 pp. | MR | Zbl

[25] Hall N. G., Hochbaum D. S., “A fast approximation algorithm for the multicovering problem”, Discrete Appl. Math., 15:1 (1986), 35–40 | DOI | MR | Zbl

[26] Hefeeda M., Bagheri M., “Randomized $k$-coverage algorithms for dense sensor networks”, Proc. 26th IEEE Int. Conf. Comput. Commun., INFOCOM-2007, Anchorage, AK, Vay 6–12, 2007, IEEE, Piscataway, 2007, 2376–2380

[27] Kononov A., Sevastianov S., Sviridenko M., “A somplete 4-parametric complexity classification of short shop scheduling problems”, J. Scheduling, 15 (2012), 427–446 | DOI | MR | Zbl

[28] Krotoszynski S., “Covering a disk with smaller disks”, Stud. Sci. Math. Hung., 28:3–4 (1993), 277–283 | MR | Zbl

[29] Megiddo N., Supowit K. J., “On the complexity of some common geometric location problems ”, SIAM J. Comput., 13:1 (1984), 182–196 | DOI | MR | Zbl

[30] Melissen H., “Loosest circle coverings of an equilateral triangle”, Math. Mag., 70:2 (1997), 119–125 | DOI | MR

[31] Melissen J. B. M., Schuur P. C., “Improved coverings of a square with six and eight equal circles”, Electron. J. Comb., 3:1 (1996), R32, 10 pp. | MR | Zbl

[32] Melissen J. B. M., Schuur P. C., “Covering a rectangle with six and seven circles”, Discrete Appl. Math., 99:1–3 (2000), 149–156 | DOI | MR | Zbl

[33] Nurmela K. J., “Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles”, Exp. Math., 9:2 (2000), 241–250 | DOI | MR | Zbl

[34] Nurmela K. J., Östergård P. R. J., Covering a square with up to 30 equal circles, Res. Rep. A62. Available at , Lab. Technology Helsinki Univ., 2000, Accessed Oct. 20, 2015 http://www.tcs.hut.fi/old/reports/A62abstract.html

[35] Tabirca T., Yang L. T., Tabirca S., “Smallest number of sensors for $k$-covering”, Int. J. Comput. Commun. Control, 8:2 (2013), 312–319 | DOI | Zbl

[36] Tarnai T., Gáspár Zs., “Covering a square by equal circles”, Elem. Math., 50 (1995), 167–170 | MR | Zbl

[37] Tóth G. F., “Packing and covering”, Handbook of discrete and computational geometry, CRC Press, Boca Raton, FL, 1997, 19–41 | MR | Zbl

[38] Tóth G. F., “Thinnest covering of circle by eight, nine and ten congruent circles”, Comb. Comput. Geom., Math. Sci. Res. Inst. Publ., 52, Cambridge Univ. Press, New York, 2005, 361–376 | MR | Zbl

[39] Verblunsky S., “On the least number of unit circles which can cover a square”, J. London Math. Soc., 24:3 (1949), 164–170 | DOI | MR | Zbl