The best known packings of unequal circles with radii of i1/2, i=1,2,3,..., in a circle (complete up to N = 72)


Last update: 08-Oct-2015

Overview    Download    Results    History of updates    References

Overview

1-12   13-24   25-36   37-48   49-60   61-72  

Download

You may download ASCII files which contain all the values of radius, ratio etc. by using the links given in the table header below.
All coordinates of all packings are packed as ASCII files here.
All packings are stored as nice PDF files here.
All contact graphs of all packings are stored as nice PDF files here.
  For industrial applications, for instance if a machine has to do an important job at every circle center,
it is useful to know a tour visiting each of the circle centers once which is of minimal length.
This problem is known as the "Traveling Salesman Problem" (TSP). Thus (very near) optimal tours are provided for every packing.
All optimal TSP tours of all packings are stored as nice PDF files here.

Results

The table below summarizes the current status of the search.
Please use the links in the following table to view a picture for a certain configuration.
Furthermore, note that for certain values of N several distinct optimal configurations exist; however, only one is shown here.
Proven optimal packings are indicated by a radius in bold face type.

Legend:
N
the number of circles; colors correspond to active researchers in the past, see "References" at the bottom of the page
radius
of the greatest circle in the container square, the latter has always a side length of 1
ratio
= 1/radius
density
ratio of total area occupied by the circles to container area
contacts
number of contacts between circles and container and between the circles themselves, respectively
loose
number of circles that have still degrees of freedom for a movement inside the container (so called "rattlers")
boundary
number of circles that have contact to the container (rattlers too if possible)
symmetry group
of the packing (Schönfliess notation); if field is empty then the packing has symmetry element C1
reference
for the best known packing so far
records
the sequence of N 's that establish density records

N radius ratio density contacts loose boundary symmetry group reference
1 0.500000000000000000000000000000 2.0000000000000000000000000000 0.785398163397448309615660845820 4 1 D4
2 0.343145750507619804793245103161 4.1213203435596425732025330863 0.554879118756540538046193810140 5 2 D1 [31]
3 0.322481442452113244255258360971 5.3710092413335613914277771031 0.653415336688284977440921006094 5 1 2 D1 [31]
4 0.301525245060630217607699590552 6.6329437841857758045605037908 0.714064166360652826049939872988 7 1 3 [31]
5 0.278593202069379960951666563040 8.0262833439235407884100010519 0.731496339964034046124443512813 11 5 [31]
6 0.262702420603488397060415948208 9.3241993627471416932560410830 0.758832749947314099521468413667 7 3 3 [31]
7 0.247311830027240142129667263463 10.6980378204033932374576320752 0.768598701155102684341386579207 15 6 [31]
8 0.233612631837004616250547378893 12.1073381285290699607688711301 0.771533931404042673492691837120 13 2 6 [31]
9 0.223488239379677023037996404806 13.4235251408616447858893789826 0.784565533603763950044558100908 11 4 4 [31]
10 0.216258275147396892561177587123 14.6226897352854604251864498691 0.808086835496466140058288102557 15 3 6 [31]
11 0.208545252245137157238246914753 15.9036216583671310147602889754 0.819788340640032328387235884221 19 2 7 [31]
12 0.200793434607503240566625259679 17.2520661440406885918411615630 0.823307830999281691083702976039 21 2 8 [31]
13 0.193952032256599718702354074282 18.5899123278781787606342603057 0.827249630453560337399554393399 25 1 7 [31]
14 0.186771833774843534029560201997 20.0333064742758261560703262828 0.821928238936539457955603878909 21 4 6 [19]
15 0.181846154442205977007149443295 21.2981316986734608032481582011 0.831090087257303794303040409923 19 6 6 [31]
16 0.177280605606302131539850081853 22.5630998174895922005097957285 0.839249810170584136970176375059 25 4 8 [31]
17 0.172714405736083360874417996418 23.8723898452221839889147487189 0.843430899233525826399851410590 31 2 10 [31]
18 0.168213670493377450854390871944 25.2217353956753314446014382775 0.844492997565612585299185400972 31 3 9 [18]
19 0.164123782849810929007088226694 26.5586063631587505437053564076 0.846238752426898018817739313933 29 5 10 [18]
20 0.160535665987108748731565533638 27.8575849640708409327678404105 0.850123927379254795534080506178 31 5 9 [18]
21 0.156677935603095648060889212028 29.2483793414578109733245121523 0.848317134571852033416529983670 35 4 13 [18]
22 0.153568099022233913362206648092 30.5429043511461404845031152447 0.852019882826972771652387352160 33 6 12 [18]
23 0.150331382513852410368140020678 31.9017323137489516144962915890 0.851982004309247807435703169592 35 6 11 [18]
24 0.147236046963912900751691145978 33.2729626106240199481138394377 0.851310879213571042882303964439 29 10 8 [18]
25 0.144597276171818916536432344472 34.5787979716762326655061284522 0.853912653643058192806346364858 37 7 9 [18]
26 0.141997358912534125226929382874 35.9092560075967280432505316469 0.855153691354888347546776329293 37 8 12 [18]
27 0.139438884989082648888977974055 37.2647301584021130388349442854 0.855156716372958744295383032278 33 11 8 [18]
28 0.137099140046940317159471880188 38.5961766085291593357615737959 0.856223880416918858644198125395 45 6 13 [18]
29 0.135063851742438071552275961313 39.8712515425949829136056787575 0.859645498269427145730483967630 43 8 9 [18]
30 0.132892984077011944750753150888 41.2153102971755825354818162348 0.859974706232609441218029806185 43 9 12 [18]
31 0.130678950163019067603561073640 42.6064362767252140178443939991 0.858383041529468373115710123686 49 7 12 [18]
32 0.128743561859373322191014467796 43.9389291999810121385666734954 0.859181381900347834416206763091 47 9 12 [18]
33 0.126802267617010333636583703893 45.3033116402044864851344901539 0.858722484290183955254825328542 54 6 14 [18]
34 0.125000275423899547093246469479 46.6475123760443015156755773062 0.859033026775064668731568595347 59 5 15 [18]
35 0.123383514378795316034519805529 47.9487054075706664041073504574 0.860868169862947611953879247750 53 9 11 [18]
36 0.121740713949523652546999021004 49.2850732129575852474779997150 0.861377036687676670534196245770 57 8 16 [18]
37 0.120059550750331711452508849319 50.6645451551584593875849268745 0.860393065652148237794899257466 55 10 14 [18]
38 0.118621079756344719822162686603 51.9672727278412643590029665121 0.862001913479725991918724222037 55 11 12 [18]
39 0.117054790272839262757935116770 53.3510673407054279902588705169 0.860910987722637986670748683741 61 9 14 [18]
40 0.115661546600271242192411990338 54.6815731437048474865695075810 0.861552455087657493129220654747 53 14 12 [18]
41 0.114195135245944635057006141179 56.0717776956285903435314232215 0.860328626527518356680097880632 67 8 13 [18]
42 0.112995984583601142134774605243 57.3537256415782037072788298182 0.862411132527223985913849419913 65 10 18 [18]
43 0.111708087433616159540381997512 58.7015557687247610001961884924 0.862465608118650711721959969018 57 15 16 [18]
44 0.110397358434834663186586195773 60.0852201062969573132024701198 0.861489035571226195287322165075 67 11 15 [18]
45 0.109316809803011556242744782848 61.3647978255816750815126607949 0.863478656355587265598254729878 73 9 16 [18]
46 0.108062183141030405916637923412 62.7632145305980586860926600372 0.862115015597984947115575648513 67 13 16 [31]
47 0.106780222354531302498859016054 64.2034119168522132608367272734 0.859691744251990316726707173195 73 11 14 [17]
48 0.105860570185622329117573712624 65.4464945553115614451371900494 0.862550268646339028330255904477 73 12 19 [31]
49 0.104539534180140988177750239798 66.9603136736548196793731584797 0.858323498652724208877744592067 71 14 16 [31]
50 0.103757995181929402220973528661 68.1496187302680226889843161081 0.862448550303300257607531489560 69 16 15 [18]
51 0.102794506645959842990589534478 69.4728605793987850481410314523 0.863103809953967033639328833797 83 10 15 [31]
52 0.101600919180121903573301659808 70.9747766961031789687485796303 0.859391434250213447986292071454 89 8 17 [31]
53 0.100791216201899349486532587351 72.2296065432667038796670266383 0.861705784265189298386380439954 83 12 19 [31]
54 0.099953782833682025813979415099 73.5186705297288311933710832199 0.863139588970673235796209404360 91 9 17 [31]
55 0.098997324164630180705597901786 74.9131206290253094349773211235 0.862094384372175842310034856736 79 16 15 [18]
56 0.098036995493924443214807996031 76.3315392913243590031586925173 0.860547245704767865598224921390 91 11 19 [31]
57 0.097312930687663775315649778479 77.5830548100822092810746798791 0.862757959496968640022254426460 97 9 18 [31]
58 0.096549763190331149521657584051 78.8792520479903153150034259254 0.863921564215682190334764604395 89 14 17 [31]
59 0.095759411202105231311888693501 80.2129592427959847601120309293 0.864239399885862062662072187233 101 9 19 [31]
60 0.095037357823174559928445907820 81.5044406729708580508148715854 0.865442900482984965630102492032 97 12 19 [18]
61 0.094322170344818894173937601302 82.8039648298409886910609859661 0.866441283623921728779601004201 102 10 22 [31]
62 0.093455246097740137010182061326 84.2543164005665619990388681317 0.864306536403357180391078873654 85 20 17 [31]
63 0.092908231184324651850609126951 85.4311166192230152725411116448 0.867777199160279766581832511570 105 11 20 [31]
64 0.092077033737400588526751554080 86.8837719383492237335364702368 0.865637124609922334589134340624 107 11 21 [31]
65 0.091389505276463910859855663023 88.2186387146891733637355169444 0.865877521332136740550473098221 101 15 19 [31]
66 0.090566157210239882645275893094 89.7028057155704753362380519219 0.863230071678161856114691473089 109 12 20 [31]
67 0.090291327855525903917209228443 90.6549163278419945476901833368 0.870804911038900292092227947865 105 15 18 [31]
68 0.089387386412057302741971162385 92.2525155084185859074343302935 0.866007087041250050278943798447 99 19 18 [31]
69 0.088698249809885753105634891700 93.6503694348236217632797100432 0.865063559533305914236272608589 113 13 20 [31]
70 0.088216546774528139460289018925 94.8416206624463792166451682195 0.867917274714125733404950389133 113 14 20 [31]
71 0.087599364147139745935716251624 96.1896225527738078847987950136 0.867869210332627430704184350993 109 17 19 [31]
72 0.087105577988006117745282373424 97.4137543224492396129163940917 0.870030887123923382087740852532 103 21 20 [31]



Updates

Please note that the results are taken from a running search. For updates look at the list below.

14-May-2013: First complete presentation from N=1 to N=72.
19-Apr-2015: Improvements for N=18–45, 47, 50, 55, and 60 by Kun He, Menglong Huang, and Chenkai Yang [17]. All these packings could be slightly improved by simple exchange heuristics [31], nevertheless the credits should go to the authors.
24-Sep-2015: The next round on the record spiral up for N=18–45, 50, 55, and 60 by Zhizhong Zeng, Xinguo Yu, Kun He, and Zhanghua Fu [18].
29-Sep-2015: A new record for an astonishing small instance of N=14 by Kun He, Mohammed Dosh, Shenghao Zou [19].

References

[1]   Ignacio Castillo, Frank J. Kampas, J\'{a}nos D. Pint\'{e}r, Solving circle packing problems by global optimization: Numerical results and industrial applications, European Journal of Operational Research 191 (2008), 786–802.
[2]   I. Al-Mudahka, Mhand Hifi, Rym M'Hallah Packing circles in the smallest circle: an adaptive hybrid algorithm, J. Operational Research Society 62 (2010), 1917–1930.
[3]   Wenqi Huang, Ruchu Xu, Two personification strategies for solving circles packing problem, Science in China (Series E) 42 (1999), 595–602.
[4]   Huaiqing Wang, Wenqi Huang, Quan Zhang, Dongmin Xu, An improved algorithm for the packing of unequal circles within a larger containing circle, European Journal of Operational Research 141 (2002), 440–453.
[5]   Wenqi Huang and Yan Kang, A Short Note on a Simple Search Heuristic for the Diskspacking Problem, Annals of Operations Research 131 (2004), 101–108.
[6]   De-fu Zhang, Xin Li, A Personified Annealing Algorithm for Circles Packing Problem, Acta Automatica Sinica 31 (2005), 590–595.
[7]   De-fu Zhang, An-sheng Deng, An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Computers & Operations Research 32 (2005), 1941–1951.
[8]   Hakim Akeb, Yu Li, A hybrid heuristic for packing unequal circles into a circular container, Service Systems and Service Management, 2006 Int. Conf. on (2006), 922–927.
[9]   Wen Qi Huang, Yu Li, Chu Min Li, Ru Chu Xu, New heuristics for packing unequal circles into a circular container, Computers & Operations Research 33 (2006), 2125–2142.
[10]   Zhipeng Lü, Wenqi Huang, PERM for solving circle packing problem, Computers & Operations Research 35 (2008), 1742–1755.
[11]   Ignacio Castillo, Frank J. Kampas, J\'{a}nos D. Pint\'{e}r, Solving circle packing problems by global optimization: Numerical results and industrial applications, European Journal of Operational Research 191 (2008), 786–802.
[12]   Mhand Hifi, Rym M'Hallah, Adaptive and restarting techniques-based algorithms for circular packing problems, Comput. Optim. Appl. 39 (2008), 17–35.
[13]   Bernardetta Addis, Marco Locatelli, Fabio Schoen, Efficiently packing unequal disks in a circle, Operations Research Letters 36 (2008), 37–42.
[14]   A. Grosso, A. R. M. J. U. Jamali, M. Locatelli, F. Schoen, Solving the problem of packing equal and unequal circles in a circular container, J. Glob. Optim. 47 (2010) 1, 63–81.
[15]   Jingfa Liu, Shengjun Xue, Zhaoxia Liu, Danhua Xu, An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle, Computers & Industrial Engineering 57 (2009), 1144–1149.
[16]   , Packing unequal circles using formulation space search, Computers & Operations Research 40 (2013), 1276–1288.
[17]   , Computers & Operations Research 58 (2015), 67–74.
[18]   Zhizhong Zeng, Xinguo Yu, Kun He, Zhanghua Fu, private communication, September 2015.
[19]   Kun He, Mohammed Dosh, Shenghao Zou, private communication, September 2015.
[31]   , program csqr, 2005–2013.
[32]   Eckard Specht, A precise algorithm to detect voids in polydisperse circle packings, Proc. R. Soc. A 471 (2015), 20150421.

Datenschutzerklärung der Otto-von-Guericke-Universität Magdeburg nach DSGVO

©  E. Specht    21-Jun-2018