Export file:

Format

  • RIS(for EndNote,Reference Manager,ProCite)
  • BibTex
  • Text

Content

  • Citation Only
  • Citation and Abstract

Optimal covering points and curves

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

Special Issues: Applied and Industrial Mathematics in Canada and Worldwide

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.
  Figure/Table
  Supplementary
  Article Metrics

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.    

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.    

6. M. E. Johnson, L. M. Moore, D. Ylvisaker, Minimax and maximin distance designs, J. Stat. Plan. Infer., 26 (1990), 131-148.    

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.    

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.    

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.    

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.    

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.    

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.    

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.    

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

Download full text in PDF

Export Citation

Article outline

Show full outline
Copyright © AIMS Press All Rights Reserved