The best known packings of unequal circles with integer radii in a square (complete up to N = 72)


Last update: 28-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.390524291751269967465540850527 5.1213203435596425732025330863 0.598902316058496912617964633019 5 2 D1
3 0.351471862576142970718986765474 8.5355339059327376220042218105 0.603693534586964887918908350083 5 1 2 D1
4 0.334735107215374257827606443309 11.9497474683058326708059105347 0.660014797288955781252450820062 5 2 2 D1
5 0.320445439141090364971641973920 15.6032802757368236130253335935 0.709709703127095853548296822042 7 2 3 [16]
6 0.308913652863248487979355956944 19.4229032753567269192072646821 0.757814603623721010446338512505 7 3 3 [16]
7 0.293884516035666854137228074093 23.8188799274829963614493876969 0.775238331434845652213766020715 11 2 5 [16]
8 0.274864248384802569160475334080 29.1052766848026548565947221833 0.756548153680051080352955284095 11 3 5 [16]
9 0.266632649665186477401509290049 33.7543058260171739525356992149 0.785844052832119069958969123370 7 6 3 [16]
10 0.259198794034443195451067480735 38.5804264146042548038100017373 0.812599508586906272187779032081 15 3 6 [16]
11 0.247163327190274524899529997838 44.5049843156215292962296113767 0.802570301380835655043784890528 15 4 6 [31]
12 0.239133461623226652957500218471 50.1811830036021152021768133626 0.810926398506644147371449674321 15 5 6 [31]
13 0.232178672614404938770668980835 55.9913615390074715473423171686 0.820713765585814877475674502682 15 6 6 [31]
14 0.226354370430404835016922439907 61.8499213131140115449042532211 0.833561431950376644576265295195 19 5 7 [31]
15 0.218890022409186872966560137635 68.5275639104253934949896137403 0.829546950559588379071016892757 17 7 6 [31]
16 0.213306762249865639384108083855 75.0093425601657328679650501142 0.835315900178288366583683639816 25 4 8 [17]
17 0.208583778822198724518803961938 81.5020232924783844083139627082 0.844211594719522809717337485129 21 7 9 [18]
18 0.203610493382765637973528765966 88.4040881240926655470237135917 0.847777243444067235492847867279 23 7 9 [17]
19 0.198431041374422615238340837823 95.7511479474050875611709149212 0.846367244410502552677752916599 25 7 9 [18]
20 0.193953211391188526069638922420 103.1176532553593928964437471333 0.847941181265758410116286524099 19 11 5 [31]
21 0.189941602299330159933657212166 110.5602971954820543114282238473 0.850962963234518673388441176205 23 10 7 [17]
22 0.185867536222651185566424825892 118.3638651864742269355044103594 0.850987881602236966636704786026 33 6 9 [18]
23 0.182534535156953538662886136594 126.0035531370723707217348427632 0.855598420797844913963135504534 25 11 6 [18]
24 0.179007777510363302934631328395 134.0723868749812685632917811262 0.856381487320259409372105475692 31 9 9 [18]
25 0.175783323971576498880735450315 142.2205442197827923530073283891 0.858138689424521070423242913681 33 9 8 [18]
26 0.172502694179796574678612354745 150.7222836351799217388244405482 0.857544513723245341081864445940 27 13 8 [18]
27 0.169771311850942424935617146420 159.0374704985830568175859862721 0.860764184294543983308097656783 35 10 10 [18]
28 0.166804484143772344247187900616 167.8611947618039004332861653669 0.860060272525310590906825686301 37 10 11 [18]
29 0.164300639058716260976107051063 176.5057042147976369559486841939 0.862685296592759148144188873495 35 12 9 [18]
30 0.161583478753433117294185768128 185.6625456478643779889146753888 0.861713316157754088198118302034 25 18 7 [18]
31 0.159189016455444919161005218863 194.7370534114489309448981459119 0.862886461777663874566625520437 45 9 14 [18]
32 0.156794336236325077466665601806 204.0890045401171263735072190047 0.862852739684479912582467424797 37 14 11 [18]
33 0.154634301277235281225126160165 213.4067262400993828367519655265 0.864271266629949977003979649551 39 14 10 [18]
34 0.152583663931115805059463247641 222.8285723650558477683168469689 0.865870450597293136772521008451 43 13 11 [18]
35 0.150356776490334985571425691398 232.7796645883121790451840742575 0.864445145958516441215576017345 37 17 10 [18]
36 0.148534265922316463099482916877 242.3683166739991704800347173545 0.866710412586128611879164030893 47 13 12 [18]
37 0.146525567454122266031481429721 252.5156574574252794190155200756 0.865901679852921492386101602644 45 15 13 [18]
38 0.144841113776026053130847645993 262.3564470704154411359250507469 0.868068644475225149280572531652 59 9 17 [18]
39 0.143010409756208450579479935147 272.7074208547738914157310180198 0.867673632306031114164796794346 41 19 10 [18]
40 0.141257743063511001827799698743 283.1703178353597892780988493546 0.867425195600521856873143617764 53 14 13 [18]
41 0.139674039607328368550897130210 293.5405900428244388767458408763 0.868507425843689842869926794592 61 11 13 [18]
42 0.138139217363138427716187783017 304.0411028939811634663023253100 0.869502220677152162335210346352 63 11 15 [18]
43 0.136448211706214453130649860683 315.1378787769161391116160535983 0.867836260550925600652373190469 46 20 11 [18]
44 0.134919219276963464344254995615 326.1210688573314301027947559736 0.867553178191774367101473095634 51 19 12 [18]
45 0.133487389219891746351059119699 337.1104960774398269506933815870 0.867892250934568883721532898090 61 15 14 [18]
46 0.131785993435762561070328383639 349.0507511515032613116863240133 0.864092243271647525645420969994 49 22 12 [17]
47 0.130457177957531807243689297280 360.2714755588234360598586137326 0.864572796237141773306397358857 57 19 13 [19]
48 0.129295038981059036099767219108 371.2439423683666479313203322257 0.866740164435480675689311790849 49 24 13 [31]
49 0.128154416952140430097243854443 382.3512381808827222172398564603 0.868710157206175024832447400037 61 19 14 [31]
50 0.127005792040726407439250357000 393.6828328582582481527793346370 0.870096100465677243430236731321 71 15 18 [18]
51 0.125619408765837343417045637744 405.9882187080443901312827071131 0.867725788339559708682839068081 77 13 16 [31]
52 0.124270598988365780378394213032 418.4416943614172373228648556937 0.865360824835647130372936202727 55 25 14 [19]
53 0.123380302595555291334877525364 429.5661372604649158359640684635 0.868944327129242614018017994838 57 25 12 [31]
54 0.122252312779396323728754458329 441.7094349572161076024507692508 0.868776805600396514796910172360 67 21 16 [31]
55 0.121457327929774301987142937353 452.8339371322295128954347665016 0.872960078525987297563183711925 75 18 17 [18]
56 0.120003660572635400848879252787 466.6524315406571583534335908258 0.867267121226477857763667673694 81 16 17 [31]
57 0.118961325243318914810235645652 479.1473185374691683976174327208 0.867084030763841529196972006403 67 24 15 [31]
58 0.118186706332806857086346191668 490.7489327663924406822736491077 0.870453872326028118814953571251 79 19 18 [31]
59 0.117305941867262604654303640915 502.9583247092579333222684668097 0.871936472336412043847537141783 75 22 19 [31]
60 0.116236341173177080662910973157 516.1896821116192721826449773530 0.870254823857264353072110563332 77 22 14 [18]
61 0.115255771628614949073193523250 529.2576600550502844486372435291 0.869542780234033550571677249608 63 30 16 [19]
62 0.114414641168952532368947470009 541.8886898263879846613393511340 0.870604085887975749516947264145 73 26 17 [19]
63 0.113723047264179613323782721469 553.9774172041878207228285377139 0.873652541044438677127578997048 74 26 14 [19]
64 0.112845760828170973845438019796 567.1458061898498036204110645474 0.873558941191014618207194194670 93 18 17 [19]
65 0.112115152220067401311425361925 579.7610645206411453591651281766 0.875445508055945480209274893043 93 19 18 [19]
66 0.111123430555051980035086716246 593.9341475540817574624502189553 0.872956113975643225333472112363 105 14 20 [19]
67 0.110110224453464134027012599532 608.4811863072370625588721796205 0.869804793342939462347279715540 107 14 19 [19]
68 0.109345514417107494311114037926 621.8819341834945755101891220628 0.870284626126575341822506561718 87 25 18 [19]
69 0.108784913748212465604796931685 634.2791258694526083002109546683 0.873775202357833512905373699672 87 26 17 [19]
70 0.108018406635983354666571087901 648.0377019066436547026751870304 0.873722615614718500690966502786 101 20 18 [31]
71 0.107115152776633913301506199030 662.8380594112164825597286478587 0.871185484329061691672784982482 99 22 18 [31]
72 0.106299591133926104121025765129 677.3309213324038895431513477744 0.869801548268957254667018701362 89 28 18 [19]



Updates

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

06-May-2013: First complete presentation from N=1 to N=72.
21-May-2013: First improvements for N=23, 40, 42, 49, 51, 54, 58, 61, 63, 64, 65, 67, 68, 70 and 72 by Eckard Specht [31].
19-Apr-2015: Improvements for N=16, 18, 19, 21–46, 49, 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.
23-Apr-2015: Further improvements for N=29, 30, 33, 35, 39, 41, 42, 44, 45, 49, 55, and 56 by Eckard Specht [31].
24-Sep-2015: The next round on the record spiral up for N=17, 19, 22–45, 50, 55, and 60 by Zhizhong Zeng, Xinguo Yu, Kun He, and Zhanghua Fu [18].
14-Oct-2015: Some small improvements (some can easily improved further) for N=52, 61–63, 66–68 by Kun He, Mohammed Dosh, Shenghao Zou [19].
19-Oct-2015: By some exchange heuristics and relocations (see [32]), some packings could be improved for N=32, 39, 42, 52, 61–68 by Eckard Specht [19].
28-Oct-2015: Some tiny improvements for N=47, 69, and 72 by Kun He, Mohammed Dosh, Shenghao Zou [19].

References

[1]   Ignacio Castillo, Frank J. Kampas, János D. Pinté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, October 2015.
[31]   , program csqn, 2005–2015.
[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