Export file:


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


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


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