Skip to main content
Log in

Packing circles in the smallest circle: an adaptive hybrid algorithm

Journal of the Operational Research Society

Abstract

The circular packing problem (CPP) consists of packing n circles C i of known radii r i , iN={1, …, n}, into the smallest containing circle ℂ. The objective is to determine the coordinates (x i , y i ) of the centre of C i , iN, as well as the radius r and centre (x, y) of ℂ. CPP, which is a variant of the two-dimensional open-dimension problem, is NP hard. This paper presents an adaptive algorithm that incorporates nested partitioning within a tabu search and applies some diversification strategies to obtain a (near) global optimum. The tabu search is to identify the n circles’ ordering, whereas the nested partitioning is to determine the n circles’ positions that yield the smallest r. The computational results show the efficiency of the proposed algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10

References

  • Addis B, Locatelli M and Schoen F (2008). Efficiently packing unequal disks in a circle. Opns Res Lett 36: 37–42.

    Article  Google Scholar 

  • Akeb H, Hifi M and M'Hallah R (2009). A beam search algorithm for the circular packing problem. Comput Opns Res 36: 1513–1528.

    Article  Google Scholar 

  • Anstreicher KM (2009). Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J Global Optim 43: 471–484.

    Article  Google Scholar 

  • Appelbaum J and Weiss Y (1999). The packing of circles on a hemisphere. Meas Sci Technol 10: 1015–1019.

    Article  Google Scholar 

  • Barclay DR and Buckingham MJ (2009). On the shapes of natural sand grains. J Geophys Res B: Solid Earth 114: B02209, (doi:10.1029/2008JB005993).

    Article  Google Scholar 

  • Birgin EG and Gentil JM (2010). New and improved results for packing identical unitary radius circles within triangles, rectangles, and strips. Comput Opns Res 37: 1318–1327.

    Article  Google Scholar 

  • Birgin EG and Sobral FNC (2008). Minimizing the object dimensions in circle and sphere packing problems. Comput Opns Res 35: 2357–2375.

    Article  Google Scholar 

  • Butler S, Graham R, Guettler G and Mallows C (2009). Irreducible Apollonian configurations and packings. Discrete Comput Geom. (doi:10.1007/s00454-009-9216-9).

  • Castillo I, Kampas FJ and Pintér JD (2008). Solving circle packing problems by global optimization: Numerical results and industrial applications. Eur J Opl Res 191: 786–802.

    Article  Google Scholar 

  • Cassioli A, Locatelli M and Schoen F (2010). Dissimilarity measures for population-based global optimization algorithms. Comput Optim Appl 45: 257–281.

    Article  Google Scholar 

  • Collins CR and Stephenson K (2003). A circle packing algorithm. Comput Geom 25: 233–256.

    Article  Google Scholar 

  • Cui Y and Xu D (2010). Strips minimization in two-dimensional cutting stock of circular items. Comput Opns Res 37: 621–629.

    Article  Google Scholar 

  • Dowsland KA, Gilbert M and Kendall G (2007). A local search approach to a circle cutting problem arising in the motor cycle industry. J Opl Res Soc 58: 429–438.

    Article  Google Scholar 

  • Fukshansky L (2009). On similarity classes of well-rounded sublattices of ℤ2. J Number Theory 129: 2530–2556.

    Article  Google Scholar 

  • Giachetti RE and Sanchez JC (2009). A model to design recreational boat mooring fields. Nav Res Log 56: 158–174.

    Article  Google Scholar 

  • Grosso A, Jamali ARMJU, Locatelli M and Schoen F (2010). Solving the problem of packing equal and unequal circles in a circular container. J Global Optim 47: 63–81.

    Article  Google Scholar 

  • Hifi M and M'Hallah R (2007). A dynamic adaptive local search based algorithm for the circular packing problem. Eur J Opl Res 183: 1280–1294.

    Article  Google Scholar 

  • Hifi M and M'Hallah R (2008). Adaptive and restarting techniques-based algorithms for circular packing problems. Comput Optim Appl 39: 17–35.

    Article  Google Scholar 

  • Huang W and Chen M (2006). Note on: An improved algorithm for the packing of unequal circles within a larger containing circle. Comput Indust Eng 50: 338–344.

    Article  Google Scholar 

  • Huang WQ, Li Y, Li CM and Xu RC (2006). New heuristics for packing unequal circles into a circular container. Comput Opns Res 33: 2125–2142.

    Article  Google Scholar 

  • Huang X and Shen L (2009). On the convergence of circle packings to the quasiconformal map. Acta Math Sci 29: 1173–1181.

    Article  Google Scholar 

  • Huang X, Liu J and Shen L (2010). Schwarz's lemma for the circle packings with the general combinatorics. Sci CHINA Math 53: 275–288.

    Article  Google Scholar 

  • Ishizaka K (2009). New spatial measure for dispersed dot halftoning assuring good point distribution in any density. IEEE T Image Process 18: 2030–2047.

    Article  Google Scholar 

  • Lazarus SB, Tsourdos A, White BA, Zbikowski R and Silson P (2009). Cooperative UAVs mapping complex environment using 2D splinegon. In: Filipe J, Cetto JA and Ferrier JL (eds). Proceedings of the International Conference on Informatics in Control, Automation and Robotics. Institute for Systems and Technologies of Information, Control and Communication; Portugal, pp 413–416.

    Google Scholar 

  • Lazos L, Poovendran R and Ritcey JA (2009). Detection of mobile targets on the plane and in space using heterogeneous sensor networks. Wirel Netw 15: 667–690.

    Article  Google Scholar 

  • Li W and Sun T (2009). Silica artificial opal incorporated with silver nanoparticles. Mater Chem Phys 116: 164–168.

    Article  Google Scholar 

  • Liu J, Shengjun X, Zhaoxia L and Danhua X (2009a). An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle. Comput Indust Eng 57: 1144–1149.

    Article  Google Scholar 

  • Liu J, Xu D, Yao Y and Zheng Y (2009b). Energy landscape paving algorithm for solving circles packing problem. International Conference on Computational Intelligence and Natural Computing. Vol. 1. IEEE Computer Society: Wuhan, China, pp. 107–110.

    Chapter  Google Scholar 

  • Locatelli M and Schoen F (2003). Efficient algorithms for large scale global optimization: Lennard-Jones clusters. Comput Optim Appl 26: 173–190.

    Article  Google Scholar 

  • Longuet-Higgins MS (2009). Snub polyhedra and organic growth. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. Vol. 456. The Royal Society: UK, pp 477–491.

    Google Scholar 

  • Lü Z and Huang W (2008). PERM for solving circle packing. Comput Opns Res 35: 1742–1755.

    Article  Google Scholar 

  • Mladenović N, Plastria F and Urosevic D (2005). Reformulation descent applied to circle packing problems. Comput Opns Res 32: 2419–2434.

    Article  Google Scholar 

  • Nordbakke MW, Ryum N and Hunderi O (2004). Curvilinear polygons, finite circle packings, and normal grain growth. Mat Sci and Eng A 385: 229–234.

    Article  Google Scholar 

  • Pinter JD and Kampas FJ (2005). Nonlinear optimization in Mathematica with MathOp-timizer professional. Math Educ Res 10: 1–18.

    Google Scholar 

  • Shi L, Olafsson S and Chen Q (1999a). A new hybrid optimization algorithm. Comput Indust Eng 36: 409–426.

    Article  Google Scholar 

  • Shi L, Olafsson S and Sun N (1999b). New parallel randomized algorithms for the traveling salesman problem. Comput Opns Res 47: 371–394.

    Article  Google Scholar 

  • Shi L and Men S (2003). Optimal buffer allocation in production lines. IIE Trans 35: 1–10.

    Article  Google Scholar 

  • Stoyan YG and Yaskov GN (2004). A mathematical model and a solution method for the problem of placing various sized circles into a strip. Eur J Opl Res 156: 590–600.

    Article  Google Scholar 

  • Sugihara K, Sawai M, Sano H, Kim DS and Kim D (2004). Disk packing for the estimation of the size of a wire bundle. Jpn J Indust Appl Math 21: 259–278.

    Article  Google Scholar 

  • Szabo PG, Markot MC, Csendes T, Specht E, Casado LG and Garcya I (2007). New approaches to circle packing in a square: With program codes. In: Springer Optimization and Its Applications. Vol. 6. Springer: New York, NY, USA.

    Google Scholar 

  • Wang H, Huang W, Zhanga Q and Xua D (2002). An improved algorithm for the packing of unequal circles within a larger containing circle. Eur J Opl Res 141: 440–453.

    Article  Google Scholar 

  • Wang YS, Teng HF and Shi YJ (2009). Cooperative co-evolutionary scatter search for satellite module layout design. Eng Comput 26: 761–785.

    Article  Google Scholar 

  • Yang YL, Guo R, Luo F, Hu SM and Gu X (2009). Generalized discrete Ricci flow. Comput Graph Forum 28: 2005–2014.

    Article  Google Scholar 

  • Zhang D and Deng A (2005). An effective hybrid algorithm for the problem of packing circles into a larger containing circle. Comput Opns Res 32: 1941–1951.

    Article  Google Scholar 

  • Zhang W and Zhang Q (2009). Finite circle method for component approximation and packing design optimization. Eng Optimiz 41: 971–987.

    Article  Google Scholar 

  • Zhu JH, Beckers P and Zhang WH (2010). On the multi-component layout design with inertial force. J Comput Appl Math 234: 2222–2230.

    Article  Google Scholar 

  • http://recmath.com/contest/CirclePacking/index.php, accessed 19 May 2010.

Download references

Acknowledgements

We thank the anonymous referees for their helpful comments and suggestions that contributed to the improvement of the presentation and contents of this paper. We are grateful to Prof Nenad Mladenović for his insight regarding the NLP models.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to M Hifi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Al-Mudahka, I., Hifi, M. & M'Hallah, R. Packing circles in the smallest circle: an adaptive hybrid algorithm. J Oper Res Soc 62, 1917–1930 (2011). https://doi.org/10.1057/jors.2010.157

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2010.157

Keywords

Navigation