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


Last update: 01-Jun-2024

Overview    Download    Results    History of updates    References

Overview

5-16   17-28   29-40   41-50   53-64   65-76   77-88   89-100  

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 circles in the container circle, the latter has always a *radius* of 1
ratio
= 1/radius, that is the radius of the circumcircle if r1=1
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
5 0.494543344330826164987430700191 4.5214802769723774026005212657 0.733719358265754275821816032965 10 9 [31]
6 0.457766152975543725896857871072 5.3509629902978928103576465111 0.733424477835101149911731099699 12 10 [31]
7 0.437359195985677791666399930707 6.0493784864906122826189130251 0.765132265252954067826997893874 10 2 9 [31]
8 0.417525212693440511396933620366 6.7742666520666042223460221198 0.784472864556162318937406976748 12 2 10 [31]
9 0.396877769095830557184664994362 7.5590023770659136880140200905 0.787559818012416982420685118199 14 2 11 [31]
10 0.380838176730934890501854004978 8.3034681221114890787043811875 0.797707442706585386146805820457 14 3 10 [31]
11 0.365584079680028318043981250480 9.0721258793824480148524528436 0.801910315892959764926966683450 16 3 12 [31]
12 0.351139294856358075190282958279 9.8653203041682594493162739373 0.801442228549432447902462851328 20 2 12 [31]
13 0.340521360740693839985942029355 10.5883262877291493139726188169 0.811683579844856236139286602192 18 4 13 [31]
14 0.329226992036486149838512132232 11.3649775907780887853061779532 0.812928092140443860424903819230 22 3 11 [31]
15 0.320958643540695773711445805821 12.0669233377924097053678542714 0.824115606907867303238986868147 24 3 8 [22]
16 0.312029237532408646549487625254 12.8193115223202231613483007121 0.827579083137978522745069428458 24 4 12 [31]
17 0.303850035311780543215753833265 13.5695413738785370522827584690 0.830923595630732547306528630353 26 4 9 [22]
18 0.296239267558937331725442215656 14.3216688391089280531406065550 0.833698184616628772004240034684 30 3 11 [22]
19 0.289909994669866366802458496248 15.0353524324138913429158350387 0.840478050094819452097260330382 32 3 10 [31]
20 0.283202939096156653144592612187 15.7912766346013912050350283677 0.842140999483364852871080684721 32 4 11 [22]
21 0.277066338318439745744292414636 16.5396335143714330088263211011 0.844423314121069238109930630304 38 2 12 [22]
22 0.271348319621250663505992517388 17.2855898513406504291917152880 0.846743971454678689998123917884 36 4 11 [22]
23 0.265697255130495150463644942363 18.0499852019821733077302951903 0.847140376606553178660406335067 34 6 9 [32]
24 0.260749430051236985140932681022 18.7880736099929804180688271362 0.849878315900561616793232014202 34 7 12 [22]
25 0.256057329455 19.5268770890 0.852349627576 40 5 12 [23]
26 0.251452883007 20.2782304685 0.853585457032 44 4 13 [23]
27 0.247086238336 21.0297119650 0.854722528449 30 12 15 [23]
28 0.243169191739 21.7605798838 0.857403209262 42 7 13 [23]
29 0.239358037197 22.4983663394 0.859384049560 42 8 12 [23]
30 0.235654723031 23.2425877343 0.860763801544 50 5 12 [23]
31 0.232015474693 23.9973836668 0.861298887952 48 7 13 [23]
32 0.228638188597 24.7415109619 0.862544451204 52 6 12 [23]
33 0.225466932338 25.4785151285 0.864200738822 52 7 13 [23]
34 0.222302570300 26.2297997139 0.864822573335 54 7 14 [23]
35 0.219295676651 26.9776398397 0.865630688360 58 6 16 [23]
36 0.216468018685 27.7177203194 0.866880457596 68 2 15 [23]
37 0.213611628920 28.4758023757 0.866968632190 64 5 16 [23]
38 0.211006154277 29.2143801402 0.868210144282 60 8 15 [23]
39 0.208452337984 29.9588772128 0.869047544223 60 9 14 [23]
40 0.205996478733 30.7022496657 0.869908259637 60 10 13 [23]
41 0.203491329952 31.4663245798 0.869583148675 68 7 16 [23]
42 0.201166881542 32.2157437085 0.870064455932 64 10 17 [23]
43 0.198939575123 32.9619610389 0.870693000105 64 11 15 [23]
44 0.196791631272 33.7069698434 0.871356288117 68 10 13 [23]
45 0.194734382458 34.4479688067 0.872194033358 66 12 14 [23]
46 0.192672434037 35.2013510237 0.872382670688 70 11 15 [23]
47 0.190746857350 35.9411142896 0.873224726137 68 13 15 [23]
48 0.188858004266 36.6847211863 0.873849971492 76 10 15 [23]
49 0.186955229932 37.4421191777 0.873806449970 68 15 13 [23]
50 0.185124507457 38.1962815674 0.873912623162 86 7 16 [23]
51 0.183171369023922940477678779650 38.9876893239256721771888571395 0.872345511182552069420580656665 80 11 17 [32]
52 0.181443019102558470864346376678 39.7430696788174040056275733364 0.872421583297862051394212299020 74 15 16 [32]
53 0.179801594382656393662743462567 40.4896848344230001198761402749 0.872872560248722970835549462560 84 11 17 [32]
54 0.178206008184517925857220002162 41.2358107519067933086136980718 0.873327987209162924366322287445 80 14 15 [32]
55 0.176648860670428038406383380694 41.9827133837675191781861570715 0.873734959332488339590600222738 82 14 19 [32]
56 0.175133045703190099890031083106 42.7293132686698430072926556672 0.874140135372356660825507620178 90 11 18 [32]
57 0.173556194429120887846667384787 43.5008065261194018733910718827 0.873530826116845556853167274678 88 13 20 [32]
58 0.172217052158318890983072517578 44.2219455647326892271917949418 0.874932035095983316919247423534 78 19 15 [32]
59 0.170758308726895401499875078247 44.9825592976184366656724825827 0.874751999978091667037267576021 82 18 18 [32]
60 0.169473802703323335301807625638 45.7059826879245299697753405003 0.876001778983111396891250779547 84 18 14 [32]
61 0.168064732480736637837007004562 46.4716752921488457169525395078 0.875618383418468751605112961763 92 15 18 [32]
62 0.166856335797149260326438581546 47.1903439350628386827473802690 0.876992659063007561156496767147 90 17 17 [32]
63 0.165496037411048899665155700006 47.9603865890740793784110793466 0.876446028760297503505567635008 96 15 18 [32]
64 0.164253152263571931982028225060 48.7053057414852438749020932978 0.876820685926904721698333623926 86 21 15 [32]
65 0.163129455448288754598257228360 49.4224524083833910498921504129 0.878170234750222446167774057884 90 20 20 [32]
66 0.161873998425335905501686408602 50.1874203619129026270907630255 0.877806910767889315666553894132 96 18 19 [32]
67 0.160800624698357688417089114680 50.9037373904931711840766535504 0.879132590714990741523171802505 94 20 18 [32]
68 0.159659100017572435358223863691 51.6488646768503941446695759674 0.879440473535531345783705049313 94 21 21 [32]
69 0.158393427977466926594870591901 52.4429830769227144944455749697 0.878096730925855088216785297626 96 21 20 [32]
70 0.157324768747260129643035063917 53.1804389859397965149062336162 0.878663441578950155576687809584 102 19 16 [32]
71 0.156227952068706937252094539404 53.9349691370891944511856435096 0.878658228272958919016224263458 98 22 15 [32]
72 0.155246749285342109724994757145 54.6567410480376660993419172119 0.879706690473804286267124931237 98 23 19 [32]
73 0.154145462005684347979334181257 55.4281886352415490233812993933 0.879150467906997444963994839883 100 23 18 [32]
74 0.153121348771001963668726383206 56.1797903172057897417838104527 0.879230529354405921361831742259 100 24 17 [32]
75 0.152249822965297142777345420175 56.8818660617973246782555892789 0.880840326532644207945262171372 113 18 20 [32]
76 0.151211815933788861417795353606 57.6528879918921842785715868197 0.880303011202770655326682822993 108 22 19 [32]
77 0.150200530438017201636200874934 58.4216604415605580010516416407 0.879847774410607542602694299157 110 22 19 [32]
78 0.149317198387173352572415203704 59.1476464983454502222279860323 0.880677216500682135485127889675 102 27 17 [32]
79 0.148462023534300718623471272709 59.8684714496165900398145908506 0.881638897275970417594635951162 106 26 17 [32]
80 0.147513552392400361670283164128 60.6335605436884042961446263868 0.881290049646730581877628688772 120 20 19 [32]
81 0.146625973913041750342316719638 61.3806664659397612506238345601 0.881466225263867995931807064059 122 20 21 [32]
82 0.145807514583589209058610151747 62.1050647766587049487024764184 0.882282999325308565049083945853 110 27 18 [32]
83 0.144882078271786006307800989878 62.8817151701394609074336812526 0.881614297382780925778847057455 126 20 24 [32]
84 0.144060147861496874449782223823 63.6203108629549090576515441921 0.882016363579744555770991308150 126 21 22 [32]
85 0.143220767724532565613589997072 64.3729579429817111329812127788 0.882024097226993889247171771643 124 23 20 [32]
86 0.142444205096573789556243332890 65.1035153673567173902066046856 0.882630293103372858820048049663 137 17 22 [32]
87 0.141634853218153793398559568101 65.8551115149762795593626877191 0.882658992429630678520974639159 128 23 20 [32]
88 0.141018867506823229515311177403 66.5218185729151843687325745596 0.884941284184359917932888059641 124 25 21 [32]
89 0.140091849673192369740059823651 67.3413989041067471488249943668 0.883157685518534808255355206356 128 25 20 [32]
90 0.139342318838405204265428742251 68.0829274235559747359870490641 0.883440822776501711273367404563 132 24 20 [32]
91 0.138577569107488247331914621787 68.8379228731468713520450207207 0.883372162348071327573597997522 128 27 18 [32]
92 0.137837569370442721543429591354 69.5867105785038085896520960274 0.883462592142749842671087602345 116 34 18 [32]
93 0.137147904510955308969024026636 70.3156989192104264978194545137 0.884048742452067432571300745700 136 25 20 [32]
94 0.136496243930316092976901225024 71.0302308375776408152585128811 0.884983168836506760520323345261 132 28 22 [32]
95 0.135703805880770751092694067425 71.8240308851211524809153246789 0.883945100665243693811044861500 142 24 23 [32]
96 0.135059209627811166179655567131 72.5456560728690440680206396921 0.884688020106518459658530508977 148 22 25 [32]
97 0.134360497832590000256288313280 73.3017364528341388145851930219 0.884584425513249685670271782281 147 23 24 [32]
98 0.133661456959656730309112689819 74.0639460454156735048410572631 0.884336561290619345084799368103 141 27 21 [32]
99 0.133018165021634478951199593509 74.8008692605849863873497249046 0.884691611286139119105371981712 138 30 21 [32]
100 0.132367940023074167893339697853 75.5469942212352626436737899839 0.884824213070584087223694137840 140 30 21 [32]



Updates

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

20-Mar-2012: First complete presentation from N=5 to N=50.
22-Mar-2012: First improvements for N=30, 36, 43, 44, 46, 49 and 50 by Eckard Specht [31].
26-Jul-2013: After sixteen months the first new records for N=19 and 20 by Lin Lu [19], great!
28-Jul-2013: Sorry Linda, but your recent improvement for N=19 was not strong enough to survive. However, your other record is much harder to beat. Further improvements for N=33, 41 and 48 by Eckard Specht [31].
30-Jul-2013: Further improvements for N=34, 37 and 38 by Eckard Specht [31].
23-Jun-2014: Improvements for N=22, 43, 49 and some new packings for N=51, 52, 60–64 and 83–85 by Eckard Specht [31].
06-Aug-2014: Improvements for N=42 and some new packings for N=53–59 by Eckard Specht [31].
27-Oct-2015: What a sensation! André Müller [32] found lots of new records, namely for N=17, 18, 20, 22–100, which are not only a little bit better than the previous, but significantly better. It seems that all other people will have no chance to beat these results for years (except for small improvements by rearrangements). So, congratulation André, for these milestones!
03-Feb-2022: He Dong [22] from Anhui Polytechnic University, China, found nine new records on his laptop, namely for N=15, 17, 18, 20, 21, 22, 24, 25, and 27. Congratulations!
01-Jun-2024: Significant improvements for N= 8, 24–50 by Jianrong Zhou, Jiyao He, and Kun He [23].

References

[22]   , private communication, January 2022.
[23]   , Solution-Hashing Search Based on Layout-Graph Transformation for Unequal Circle Packing, submitted to European Journal of Operational Research, under review, May 2024.
[31]   , program ccir, 2005–2024.
[32]   , private communication, October 2015.
[33]   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    01-Jun-2024