Optimal covering points and curves

Justin Tzou; Brian Wetton; Justin Tzou; Brian Wetton

doi:10.3934/math.2019.6.1796

AIMS Mathematics

2019, Volume 4, Issue 6: 1796-1804. doi: 10.3934/math.2019.6.1796

Previous Article Next Article

Research article Special Issues

Optimal covering points and curves

Justin Tzou ¹,
Brian Wetton ^{2
,
,}

1.
Department of Mathematics and Statistics, Macquarie University, 12 Wally’s Walk L6, Sidney, Australia
2.
Mathematics Department, University of British Columbia, #121 Mathematics Road, Vancouver, BC, Canada V6T 1Z2

Received: 26 June 2019 Accepted: 10 July 2019 Published: 03 January 2020
MSC : 11H31, 49M15

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.
- covering,
- regularized Newton method,
- experimental design,
- optimal networks,
- fuel cell channels
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

Related Papers:

Abstract

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.

References

[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

Reader Comments

Your name:*

Email:*
© 2019 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)