Research article Special Issues

Optimal covering points and curves

  • 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.

    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:

  • 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
  • Reader Comments
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3598) PDF downloads(321) Cited by(1)

Article outline

Figures and Tables

Figures(3)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog