The best known packings of variable sized circles in a square with maximum sum of perimeters (complete up to N = 100)

Last update: 19-Jul-2012

Overview    Download    Results    History of updates    References

Overview

1-12   13-24   25-36   37-48   49-60   61-72   73-84   85-96   97-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
sum radii
total sum of the radii of all circles in the square
sum perimeter
total sum of the perimeter of all circles in the square
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
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 sum radii sum perimeter density contacts boundary symmetry group reference
1 0.500000000000000000000000000000 3.141592653589793238462643383280 0.785398163397448309615660845820 4 1 D4
2 0.585786437626904951198311275790 3.680604738042440459818811552997 0.539012084452647221356168169717 5 4 D2 [1]
3 0.796287456147963457998020502953 5.003221644760293276135485596786 0.678218187441287144901808966164 9 6 D1 [1]
4 1.006788474669021964797729730115 6.325838551478146092452159640576 0.817424290429927068447449762610 13 8 D2 [1]
5 1.103553390593273762200422181052 6.933830449463872981201905569950 0.819086418675738760950421356427 16 8 D4 [1]
6 1.202838910872078657381838741465 7.557659771695340778922021888422 0.830664461673435029980087658912 19 10 D1 [1]
7 1.306546350756615445454939160966 8.209272834223072556003704216547 0.832372446739921510777449088983 22 10 D1 [1]
8 1.423813915317852118982452473015 8.946086672882968393638492825097 0.817424290429927068447449762610 24 12 D4 [1]
9 1.524365359370580005965829505370 9.577870028770758465988783427985 0.839665382935197182568517399731 28 12 D1 [1]
10 1.591012852634175543986419312660 9.996628579204932416981624073924 0.840405214793719599429969588643 31 12 D1 [1]
11 1.680058380779223617959921165038 10.556118133315944812866100669395 0.845401576001727384873104329117 34 12 D1 [1]
12 1.765978318168770851858655456264 11.095969021515737987134550301943 0.842428591981169951285040911048 37 12 D2 [1]
13 1.829542411691333203627092256054 11.495354000000890880372024282552 0.843172230055828974197539438121 39 14 [1]
14 1.905667205295632195846502086978 11.973660184687500863809988111014 0.847885561042347293067793504317 43 14 D1 [1]
15 1.980266508443774096901922635106 12.442381430153741926905910549675 0.846184875219799824891693060931 45 16 [1]
16 2.053080418438583981987901509732 12.899884719591428236703614279332 0.853389973898101396941616149366 49 16 D1 [1]
17 2.111185327828211240022631137571 13.264968632543335418563471346637 0.850943221105067392431213712790 51 16 [1]
18 2.178530295968693807223893561829 13.688109546876092842259078467585 0.856434344550151323660923525506 55 16 D1 [1]
19 2.236704571293945055232413399827 14.053629298855531442982966837068 0.853822984295342350318940227000 57 16 [1]
20 2.301122834498313413764291680781 14.458381183735246100464690890853 0.854890113387527700317117027741 60 16 [1]
21 2.362117319375049000968022108655 14.841620834931738632758072759040 0.855805001848011565634624308602 64 16 D2 [1]
22 2.420202649748443654040494930111 15.206581729296524080498195694397 0.858428348511724529164595642912 66 17 [1]
23 2.478013611962867680511965960870 15.569818717676107374123270815121 0.858563010052848740163200721833 69 20 [1]
24 2.530311586970656497332856431156 15.898416585840291287613179759034 0.860593386357725359616549829273 72 20 [2]
25 2.587275055271924779311284868238 16.256328612916810274990844226348 0.863260424816845045690301939447 76 20 D2 [1]
26 2.634292402071373692434737688353 16.551747315509674841291329900645 0.863469550270375261897895680918 78 20 [1]
27 2.685350025228333453141754261406 16.872551823148996623218829705597 0.864506713225970174045840953681 82 20 D1 [1]
28 2.737739985532671657006016690907 17.201727651976936202494845747546 0.862283425198561111994790800054 84 20 [1]
29 2.790344154625654102112663366889 17.532249394318354015796852965287 0.862992740830348261756470643847 87 20 [1]
30 2.842668747464101322725138690987 17.861014507245039806328552289543 0.863678798205131171009202876861 90 20 [1]
31 2.889969851932196898216302259992 18.158216111852344615232440759489 0.863902357567333889164648100476 93 20 [1]
32 2.936526266450276479209251990128 18.450738691507304626845634158958 0.865148949406078485460464925644 97 20 D1 [2]
33 2.987285008591274169537954205693 18.769665274338538620714132782894 0.867066089446824809394706882928 99 23 [2]
34 3.025864907863668557567563507480 19.012069930599315458481492371313 0.869696171561518255580687935802 103 24 D1 [1]
35 3.072617273880799168525504325782 19.305823709834032716253297303482 0.869951624674341876300877176682 105 24 [2]
36 3.121754486100678094044373444038 19.614561919689741213220901304159 0.869881804497196671621561331965 109 24 D2 [1]
37 3.161498916177463300640419978364 19.864283538790424467275033632777 0.870181953643592778220277319633 111 24 [1]
38 3.205945627972098690702456784649 20.143550465290923179917149272164 0.870613578472563571705327848721 115 24 D1 [1]
39 3.245853505628339299715118934080 20.394299055821334686472089487883 0.868746481669291230989909202269 117 24 [2]
40 3.290893702724696117928611244330 20.677294960449636520216929612560 0.871368019797920779202616909182 121 24 D2 [1]
41 3.336245021959755658254445768287 20.962245703128573586907725420037 0.870463471234243540129722648286 123 24 [1]
42 3.378962665659605833087364742053 21.230648574380804834653908860960 0.870373026628510042855500942791 126 24 [2]
43 3.422605518048386902248531568227 21.504864703273401566150574606071 0.868635886925333986717721834535 129 24 [1]
44 3.466043568236472105890131560952 21.777794021987707990533360586245 0.872329991513180343723449293994 132 25 [2]
45 3.503095055215206802979957726455 22.010595380581649606750606110288 0.871496118602630708189372660891 135 26 [1]
46 3.539568936861041916662603279795 22.239767537834567986690644720081 0.872596494882125136814529104501 138 28 [2]
47 3.578327279825326942741153041171 22.483293388878390962571918332157 0.875521967334618845749777159555 141 29 [2]
48 3.611772532096401294028855848933 22.693436106542920022712608832483 0.874407260503713246187816390777 144 28 [2]
49 3.655413576540647294829666924131 22.967640875784977817058857212517 0.874887674201615558764955720410 148 28 D2 [1]
50 3.686474098749043425299880476770 23.162799892558097625819823496456 0.874020655270805011102907782514 150 28 [1]
51 3.725628939337988388800786200862 23.408817011651515526996305469658 0.874063044823362691967955678791 153 28 [2]
52 3.760937808393237000868765201114 23.630669178912581572971822386050 0.874512644141055236797839550731 156 28 [2]
53 3.802123351322513485488370158075 23.889445577114025687829259654719 0.875747343884076558314821642535 159 28 [2]
54 3.835746197135058392118506486744 24.100704147908972529869096189080 0.876747215112531870487359916887 162 29 [2]
55 3.875731308209674269634748773529 24.351938010318942777375417911889 0.875432311384390470654786403703 165 28 [2]
56 3.917863535460591530417986221576 24.616662601540657490858350548307 0.875094556531656754083600838274 168 28 [2]
57 3.946872146995363516705549549401 24.798929083317617109041597863378 0.876214003514097316678795771190 171 29 [2]
58 3.986578874657524016277112218930 25.048413811160685211156499455905 0.876441368980443758212584724756 174 30 [2]
59 4.021453148285642304105007560929 25.267535334819438567230930615190 0.876172595083608002213622156942 177 30 [2]
60 4.057375010904168044097205536891 25.493239054230683123503466426459 0.877801322733081463411903682725 180 31 [1]
61 4.081403795766376348959318149786 25.644216362226289609004668708481 0.876814077489675734775860191103 183 29 [2]
62 4.117005967583860717732512046145 25.867911405093590549190160964960 0.875322852043508111349476510108 186 31 [2]
63 4.151017533531418817754867685785 26.081612376529457153082696303347 0.878298173110172323229666542741 189 32 [2]
64 4.190585830356899664400224070736 26.330227317773439082959541894733 0.878610892804071448191508407817 193 32 D1 [1]
65 4.218091021409525880798722132393 26.503047530066467549955885434640 0.877656702455251687993015628805 195 32 [2]
66 4.251441553084215722321206032550 26.712595100671506170479157518899 0.878304227174041121911602640763 198 32 [2]
67 4.285588116687675748270323787111 26.927144287395439440941143534862 0.877930307445240241256264953429 201 32 [2]
68 4.320867327804372335416206235613 27.148810108332754168906348152869 0.877761536986033317786067154903 204 32 [2]
69 4.352742800223998362793040436148 27.349089608299156566347422338151 0.879840899514467856951926776726 207 33 [2]
70 4.392179819751614777393841172509 27.596879709954030458696592164146 0.879139148526893856659116192345 210 32 [2]
71 4.423446251008178063907168593874 27.793332491433209476068155145319 0.879309092241100110497105553532 213 33 [2]
72 4.458515412632491712391792295250 28.013678532486203193371139556444 0.879964231925716591470309617504 216 33 D1 [1]
73 4.487637388110017918068373071308 28.196657300922640070562805409571 0.880202644997138179881725164517 219 34 [2]
74 4.512597355466506010906697694849 28.353485401084608159206740470518 0.880759462746072785488117746775 222 34 [2]
75 4.544061893758860615119720262640 28.551182925780320084411808908535 0.881541051639166054317392518718 225 35 [2]
76 4.572442898482126662643248092668 28.729506037660539759913453979747 0.881132732661970802583094597042 228 35 [2]
77 4.600599294845713218790783131134 28.906417893595351547348225122997 0.881616261480305808055766865321 231 36 [2]
78 4.629788480014697463516565562523 29.089818952977657648852571251749 0.881413275058700657872227936022 234 36 [2]
79 4.660114059296925647001157306403 29.280360187155463441488271983890 0.882623702433218201684972137183 237 37 [2]
80 4.685279827121866341903732792793 29.438481369797023595429304912678 0.882249450600530469205598619944 240 38 [2]
81 4.726033735176005295558176099438 29.694545726092937280335636935962 0.881670504104991637794877602937 244 36 D2 [1]
82 4.749812789170481656274499982239 29.843953928769661205678759328501 0.881347513148746049876625338652 246 36 [2]
83 4.779791487288661334067406701502 30.032315644314180075550995628314 0.880840748155417166245006407580 249 35 [2]
84 4.812216737075852468886491872750 30.236049497358687427019631739854 0.881493366679790703382020668964 252 36 [2]
85 4.840788086403362043782998866988 30.415568579659590946877909637518 0.881747556313213570233196207701 255 36 [2]
86 4.872576585907265236260309804024 30.615301612679801059634389848474 0.881001774718750619112127713376 258 36 [2]
87 4.901146191845337529348800962246 30.794809740941807558349357300262 0.883067868131224446663871279086 261 37 [2]
88 4.930407819813363004509547640523 30.978665971854660482356930425253 0.882728837695965712759883930692 264 38 [2]
89 4.963123644181661717967729160537 31.184225558837822834982388922153 0.882383329825467714881737350311 267 37 [2]
90 4.996999276703750317538190979480 31.397072435372024882253978692376 0.883087421246006876139544606454 270 38 [1]
91 5.014791358242512136980896311479 31.508863380680514314389685432878 0.881380446719313343931156351046 273 37 [2]
92 5.042913382821467269401002816170 31.685559272323148399142078847716 0.882868632510442917362203741155 276 38 [2]
93 5.067858107544388710806540009781 31.842291600193847781127472132822 0.884077998027693143183653840838 279 40 [2]
94 5.095772569677371129692591058596 32.017683338525623855471354028371 0.883669063676683456522316973519 282 40 [2]
95 5.112120994032325481921483982492 32.120403518228209949984822554641 0.884830603515974889186833941453 285 41 [2]
96 5.134703801820040400210134686534 32.262295484314841066570454894600 0.884418749826929075863875587138 288 39 [2]
97 5.175713921633106673088193032464 32.519969666569973521870636168290 0.883243241514298816795439522933 291 40 [2]
98 5.199716369613184117225403805106 32.670781495054738462665996760798 0.883862832436736284764047802673 294 40 [2]
99 5.226424247039071498065175170195 32.838592038083027409008229034610 0.883832406813993131545774044774 297 40 [2]
100 5.261573443981024547162646712993 33.059440955867868459426870254597 0.884045506368443170208011725567 301 40 D1 [1]



Updates

For updates look at the list below.

10-Dec-2011: First complete presentation from N=1 to N=32. All these packings were found by David Cantrell [1].
30-Dec-2011: One small improvement for N=25 and new results up to N=40 by Eckard Specht [2].
31-Dec-2011: Improvements for N=35 and 40 and new results up to N=60 by Eckard Specht [2].
01-Jan-2012: One rigorous improvement for N=33 and one small improvement for N=54 by Eckard Specht [2].
02-Jan-2012: Some more improvements for N=37, 41, 42, 43, 44, 45, 46, 54, 55, 56, 57, 58, 59 and 60 by Eckard Specht [2].
03-Jan-2012: More improvements for N=34, 35, 36, 37, 38, 40, 41, 44, 47, 48 and 49 by Eckard Specht [2].
06-Jan-2012: Further improvements for N=35, 49, 50, 51, 52, 54, 55, 56 and 58 by Eckard Specht [2].
09-Jan-2012: Even more improvements for N=24, 34, 40, 47, 48, 49, 50, 51, 52, 53, 54, 55 and 56 by Eckard Specht [2]. The case N=24 was the second improvement of Cantrell's initially conjectured record packings.
10-Jan-2012: Applying the right heuristics gave an enormous boost: the packings for N=34, 35, 36, 37, 38, 39, 40, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 58, 59 and 60 are much better than before. And that's not the end ...
11-Jan-2012: More improvements for N=35, 36, 40, 48, 49, 50, 54, 56, 57, 59 and 60 by Eckard Specht [2].
12-Jan-2012: New results up to N=80 by Eckard Specht [2].
13-Jan-2012: Further improvements for N=36, 37, 41, 46, 77 and 79 by Eckard Specht [2].
15-Jan-2012: Improvements for N=52, 64, 70, 71 and 75 and new results up to N=100 by Eckard Specht [2].
17-Jan-2012: Improvements for N=66, 82, 83, 85, 88, 89, 91, 93, 94, 95, 96, 98 and 99 by Eckard Specht [2].
19-Jan-2012: Improvements for N=64, 81, 85, 90, 92, 95 and 96 by Eckard Specht [2].
20-Jan-2012: New packings for N=62, 90, 91 and 93 by Eckard Specht [2].
22-Jan-2012: More better packings for N=58, 71, 72, 82, 85, 89, 90, 95, 96 and 97 by Eckard Specht [2].
23-Jan-2012: More packings for N=61, 89, 91 and 98 by Eckard Specht [2].
24-Jan-2012: Even more packings for N=46, 61, 62, 64, 74, 79, 83, 85, 91, 94 and 99 by Eckard Specht [2].
25-Jan-2012: Improvements for N=51, 56, 57, 58, 62, 70, 76, 83, 84, 85, 86, 87, 88, 89, 92, 95, 96, 97 and 98 by Eckard Specht [2].
26-Jan-2012: Improvements for N=32, 34, 36, 41, 42, 43, 44, 46, 47, 53, 54, 58, 60, 61, 63, 64, 65, 67, 68, 69, 71, 72, 75, 79, 80, 81, 82, 91, 94, 95, 97, 98 and 100 by Eckard Specht [2].
27-Jan-2012: David Cantrell [1] sent me nice packings for N=45, 60, 72 and 90. So I don't have to compete for myself. ;-)
27-Jan-2012: Three better packings for N=34, 43 and 44 by Eckard Specht [2].
28-Jan-2012: Better packings for N=37, 59, 65, 66, 73, 76, 88, 89, 92, 94, 95, 96 and 98 by Eckard Specht [2].
29-Jan-2012: For some square numbers, namely for N=25, 36, 49, 64, 81 and 100, David Cantrell [1] found these beautiful packings.
29-Jan-2012: Improvements for N=59, 95 and 99 by Eckard Specht [2].
31-Jan-2012: Two improvements for N=27 and 34 by David Cantrell [1]. Please note that all these packings have a high symmetry and 3 N + 1 contacts.
06-Feb-2012: Four improvements for N=37, 38, 40 and 41 by David Cantrell [1].
David gave the following symmetry puzzles:
  1. None of the current packings has symmetry group C2. Is it impossible for an optimal max-perimeter packing to have that symmetry? Or have we just not encountered such a packing yet? But some packings come close to having that symmetry, such as N = 39 and N = 41.
  2. Many of the packings have symmetry group D1. But the axis of symmetry is almost always a diagonal of the square, rather than a vertical or horizontal line. Indeed, unless I've overlooked something, the first D1 packing having a vertical or horizontal axis of symmetry is N = 72. In D1 packings, why is a diagonal axis of symmetry so much more frequent than a vertical or horizontal axis?

19-Jul-2012: Two improvements for N=43 and 50 by David Cantrell [1].

References

[1]   , private communication, July 2011, January–July 2012.
[2]   , program csq, December 2011–February 2012.

©  E. Specht     19-Jul-2012