We consider the optimal covering of the unit square by N circles. By optimal, we mean the covering that can be done with N circles of minimum radius. Equivalently, we study the problem of the optimal placement of N points such that the maximum over all locations in the square of the distance of the location to the set of points is minimized. We propose a new algorithm that can identify optimal coverings to high precision. Numerical predictions of optimal coverings for N = 1 to 16 agree with the best known results in the literature. We use the optimal designs in approximations to two novel, related problems involving the optimal placement of curves.
Citation: Justin Tzou, Brian Wetton. Optimal covering points and curves[J]. AIMS Mathematics, 2019, 4(6): 1796-1804. doi: 10.3934/math.2019.6.1796
We consider the optimal covering of the unit square by N circles. By optimal, we mean the covering that can be done with N circles of minimum radius. Equivalently, we study the problem of the optimal placement of N points such that the maximum over all locations in the square of the distance of the location to the set of points is minimized. We propose a new algorithm that can identify optimal coverings to high precision. Numerical predictions of optimal coverings for N = 1 to 16 agree with the best known results in the literature. We use the optimal designs in approximations to two novel, related problems involving the optimal placement of curves.
[1] | O. Berman, Z. Drezner, A new formulation for the conditional p-median and p-venter problem, Oper. Res. Lett., 36 (2008), 481-483. doi: 10.1016/j.orl.2008.02.001 |
[2] | G. Buttazzo, E. Oudet, E. Stepanov, Optimal transportation problems with free dirichlet regions, In: G. dal Maso, F. Tomarelli, Editors, Variational Methods for Discontinuous Structures, Birkhäuser Verlag, Basel, 51 (2002), 41-65. |
[3] | G. Buttazzo, A. Pratelli, S. Solimini, et al. Optimal Urban Networks via Mass Transportation, Springer, Berlin, 2009. |
[4] | Z. Drezner, The p-centre problem - heuristic and optimal algorithms, J. Oper. Res. Soc., 35 (1984), 741-748. |
[5] | A. Heppes, H. Melissen, Covering a rectangle with equal circles, Period. Math. Hung., 34 (1997), 65-81. doi: 10.1023/A:1004224507766 |
[6] | M. E. Johnson, L. M. Moore, D. Ylvisaker, Minimax and maximin distance designs, J. Stat. Plan. Infer., 26 (1990), 131-148. doi: 10.1016/0378-3758(90)90122-B |
[7] | W. C. Ke, B. H. Liu, M. J. Tasi, Efficient algorithm for constructing minimum size wireless sensor networks to fully cover critical square grids, IEEE T. Wirel. Commun., 10 (2011), 1154-1164. doi: 10.1109/TWC.2011.021611.100123 |
[8] | J. B. M. Melissen, P. C. Schuur, Improved coverings of a square with six and eight equal circles, Electron. J. Comb., 3 (1996), 1-10. |
[9] | F. Morgan, R. Bolton, Hexagonal economic regions solve the location problem, Am. Math. Mon., 109 (2002), 165-172. doi: 10.1080/00029890.2002.11919849 |
[10] | K. J. Nurmela, P. R. J. Östergård, Packing up to 50 equal circles in a square, Discrete Comput. Geom., 18 (1997), 111-120. doi: 10.1007/PL00009306 |
[11] | K. J. Nurmela, P. R. J. Östergård, Covering a square with up to 30 circles, Research report, Helsinki University of Technology, Laboratory for Theoretical Computer Science, 2000. |
[12] | J. Schaer, The densest packing of 9 circles in a square, Can. Math. Bull., 8 (1965), 273-277. doi: 10.4153/CMB-1965-018-9 |
[13] | D. Spernjaka, A. K. Prasada, S. G. Advani, Experimental investigation of liquid water formation and transport in a transparent single-serpentine PEM fuel cell, J. Power Sources, 170 (2007), 334-344. doi: 10.1016/j.jpowsour.2007.04.020 |
[14] | Specht, The best known packings of equal circles in a square, Available from: http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html, accessed November 1, 2012. |
[15] | T. Tarnai, Z. Gaspar, Covering a square by equal circles, Elem. Math., 50 (1995), 167-170. |
[16] | Y. G. Stoyan, V. M. Patsuk, Covering a compact polygonal set by identical circles, Comput. Optim. Appl., 46 (2010), 75-92. doi: 10.1007/s10589-008-9191-8 |
[17] | A. E. Xavier, A. A. F. de Oliviera, Optimal covering of plane domains by circles via hyperbolic smoothing, J. Global Optim., 31 (2005), 493-504. doi: 10.1007/s10898-004-0737-8 |