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


Last update: 02-Jun-2024

Overview    Download    Results    History of updates    References

Overview

5-16   17-28   29-40   41-52   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.570922096619039327572248540682 1.7515524550931378665568811273 0.744257158931325262919831649210 8 1 8 [1]
6 0.552462703778895858181919898120 1.8100769394203586063526115504 0.747776845713385678253134806798 12 10 [1]
7 0.543855392719099794562810055793 1.8387240678084035628744535299 0.766911884377439960701417861841 12 1 10 [1]
8 0.538097011594676918415207784095 1.8584009545722078860518310212 0.786951170528927642877892446330 14 1 10 [31]
9 0.532251017145950947776483149073 1.8788127552338439170686917244 0.801421656550761748912120728233 14 2 11 [2]
10 0.522620172967119285734658120347 1.9134355153621579135747986081 0.799994503715671817039971557739 18 1 11 [31]
11 0.518352866238196249839914019637 1.9291877505322305145432013482 0.811409919523441134848081636471 20 1 13 [31]
12 0.512866950316335641876274515984 1.9498234374104265275455335062 0.816245289797483039072781824356 18 3 11 [31]
13 0.508844527279375491914800119383 1.9652368186932685571530009639 0.823408986603556154663566884407 22 2 13 [31]
14 0.504987063495310980797764145277 1.9802487475192231818475507113 0.829187198385919487092411030112 16 6 10 [16]
15 0.501829350259971028078346639563 1.9927092735447883259424864242 0.835638555906221923856147111261 18 6 11 [31]
16 0.498856178168462934962144041161 2.0045857779520204648299050634 0.841319719781977370987306980855 22 5 14 [16]
17 0.496214433802134310366198114497 2.0152577834903334777242732148 0.846916767441465729418659584290 30 2 14 [17]
18 0.493060522668214360455819502949 2.0281485822236686639861103870 0.849691107900951254052871420972 28 4 16 [17]
19 0.489716608581961948150612639469 2.0419973153363736119166355332 0.850827285608816047609664462513 34 2 15 [17]
20 0.487462145681 2.0514413455 0.854892535313 34 3 12 [20]
21 0.484888190971411805794536944239 2.0623311077067626961925510750 0.857084190404219922580654549281 32 5 15 [17]
22 0.483567606273408313065930244471 2.0679631700445246082006019953 0.863051022601780021218709439771 32 6 14 [17]
23 0.480821851142213573402595165555 2.0797723681327206147789405733 0.863329556915647433132889131557 36 5 15 [17]
24 0.478381196872302363133524238449 2.0903831641755288099475223776 0.864122627549923203618044223198 34 7 15 [17]
25 0.476751718388099055418281177941 2.0975278356227159485165655764 0.867337533092140648556940206836 40 5 13 [19]
26 0.474603330816 2.1070227179 0.868201571904 34 9 10 [20]
27 0.473222670592 2.1131701039 0.871451642173 44 5 10 [20]
28 0.471370007341 2.1214756655 0.872576891457 52 2 16 [20]
29 0.469908040244 2.1280759518 0.874786903436 36 11 11 [20]
30 0.468111875195 2.1362414692 0.875416447171 42 9 13 [20]
31 0.466511538255 2.1435697041 0.876461515337 50 6 16 [20]
32 0.464833270522 2.1513090035 0.876918932625 46 9 11 [20]
33 0.463676655479 2.1566753214 0.879075430314 60 3 19 [20]
34 0.462334598612 2.1629356812 0.880280897607 46 11 14 [20]
35 0.460853371077 2.1698875668 0.880717611985 48 11 16 [20]
36 0.459301870582 2.1772173467 0.880657528681 50 11 13 [20]
37 0.458026808993 2.1832783155 0.881444714186 64 5 22 [20]
38 0.457010575847 2.1881331699 0.883033976318 56 10 15 [20]
39 0.455540870731 2.1951927132 0.882684553380 68 5 19 [20]
40 0.454540624932 2.2000233756 0.883977710556 52 14 12 [20]
41 0.453527830785 2.2049363504 0.885059560770 70 6 21 [20]
42 0.452554740096 2.2096774410 0.886141990686 42 21 13 [20]
43 0.451235263946 2.2161388524 0.885717415048 50 18 12 [20]
44 0.450177826296 2.2213444146 0.886176958757 74 7 18 [20]
45 0.449194559799 2.2262068366 0.886793963445 52 19 13 [20]
46 0.448304812076 2.2306251752 0.887653455983 64 14 18 [20]
47 0.447539197551 2.2344411517 0.888885695194 76 9 21 [20]
48 0.446395997097 2.2401634569 0.888501776374 62 17 16 [20]
49 0.445518731290 2.2445745370 0.889063760923 84 7 20 [20]
50 0.445013975690 2.2471204381 0.891011100754 70 15 18 [20]
51 0.440360204780834877424274931465 2.2708682327407289552468575692 0.876275192574855102788946680107 88 7 19 [31]
52 0.438737534208946995395549468254 2.2792670378727022719975100259 0.873530911463137469668759196388 74 15 25 [31]
53 0.438256971957934379970069570475 2.2817663242924608058369409609 0.875242297449042416667930908844 72 17 23 [31]
54 0.437728873361506530982868568884 2.2845191643872470846091174993 0.876682508345191804310195556329 84 12 26 [31]
55 0.437455405608712459240375530234 2.2859472924069035149882670676 0.879066853401257754151297826429 91 8 27 [31]
56 0.437449234459481512537057744413 2.2859795405416909772966604735 0.882459227305797841928652349324 92 8 27 [31]
57 0.436960869636605641615405860089 2.2885344420694706718633190693 0.883839719671695240242653026407 80 17 25 [31]
58 0.436173677605725492433623617766 2.2926647144075008838287219035 0.883938214126953734859917316780 90 13 31 [31]
59 0.435483678314617948097572936155 2.2962973121521758880449027698 0.884358096582639398500089249851 102 8 31 [31]
60 0.433556977255135657859784873352 2.3065019189197112506888876097 0.879682975132927932884872208514 93 13 19 [31]
61 0.432653272144755016903344839836 2.3113196279385236873667427101 0.879088248725578397989652553797 102 10 26 [31]
62 0.431502827821605475738461859628 2.3174819155841687411034902303 0.877422534878202866824569452752 102 11 26 [31]
63 0.431258045158287127212529027771 2.3187973215269856203781345177 0.879379448859261256480686670592 93 15 23 [31]
64 0.430852418904905569425587101367 2.3209803545763829289138564155 0.880626527860317661054834551472 108 10 33 [31]
65 0.430761577071681762755651136889 2.3214698181718119005990257968 0.883109921255195082142109142303 108 11 32 [31]
66 0.430225417154745386520632168972 2.3243629040176293535990062035 0.883717365705314882662133307333 112 9 28 [31]
67 0.428776519103276460565290917490 2.3322172634158095204955625102 0.880519103518679370074059211145 94 20 21 [31]
68 0.428397160759324055923530484555 2.3342825107139438933099512604 0.881660605344986297535994212401 100 18 19 [31]
69 0.427150718245698764876014211140 2.3410940384391349338593512799 0.879181914641841987443042654188 106 16 24 [31]
70 0.426531030158597640271093297723 2.3444953105244619040358592774 0.879231803778946372371807881344 120 10 24 [31]
71 0.425860637931413626912875614709 2.3481860283153324985532197052 0.879024471183384653611742740352 111 15 27 [31]
72 0.425745315994553169964247723557 2.3488220831366554239931249538 0.881065947769554914962166391162 115 14 27 [31]
73 0.426032716940996043524949107714 2.3472375717531954324539110198 0.884742237371386559337411141411 113 16 30 [31]
74 0.425523773855380861518148294851 2.3500449597438038267440417590 0.885076553951943994622909434378 106 21 32 [31]
75 0.425133471666491411898794343519 2.3522024649813499583116938522 0.885863511373219946826700946955 116 17 33 [31]
76 0.424998653802295377885533387669 2.3529486294918685075375367517 0.887678381993589583172800033575 111 20 32 [31]
77 0.424157469101681673684116750779 2.3576149728493258329442433503 0.886504446816761194934633915112 114 20 37 [31]
78 0.424733661668767710808780505376 2.3544166385848146241546172254 0.891227412966785883795989006574 120 18 35 [31]
79 0.424586549240146372436384982298 2.3552324061834551461742722998 0.892892087839937600851710705690 140 9 41 [31]
80 0.424230237595502595360608442242 2.3572105695904815667286113511 0.893643733596767710517955541124 116 22 31 [31]
81 0.423932713477199351185321951938 2.3588649052293145343816511500 0.894609452607229897327818408698 137 12 36 [31]
82 0.423330407066137626506540872656 2.3622210531259293789932496821 0.894254679891509388641271594889 148 7 40 [31]
83 0.422906919880933563461436349095 2.3645865153531724906989979647 0.894621225528453595138637043396 141 11 39 [31]
84 0.422361597304521599246636202377 2.3676394974872742366907783830 0.894439234510393157411860378831 134 16 35 [31]
85 0.422101078704352803591098274706 2.3691007923256647426413958572 0.895432278950842221664547936792 154 8 38 [31]
86 0.421097830899252137556891879325 2.3747450749496985420199913423 0.893242718960062375231081125647 122 25 30 [31]
87 0.420575348556055512631411809936 2.3776952297210474165884789641 0.893060635292557222715438103157 147 12 41 [31]
88 0.420440658355645988565645310164 2.3784569358991711305221190185 0.894497471481308588391873349401 132 22 32 [31]
89 0.419701663884017720626144063781 2.3826448309634163814834737265 0.893334986122094372072570070922 156 11 39 [31]
90 0.418741542862895202318336783611 2.3881079320745136932092054760 0.891200697992562979683840605497 133 22 33 [31]
91 0.416457790480585079238075356553 2.4012037302652384411484252908 0.883412163542492751622633428755 130 25 22 [31]
92 0.416367083684975670145045258132 2.4017268395707341460508653526 0.884911746058287392473387191976 117 33 26 [31]
93 0.415969258974355233127383318018 2.4040238032629488853427498960 0.885082089429181204191849475282 152 17 31 [31]
94 0.415939226698482579503457008460 2.4041973822413902621835789715 0.886794774595103546685990011101 142 23 24 [31]
95 0.414803130485607371904840569289 2.4107821916129379151402484324 0.883768184012481667692708535664 134 28 25 [31]
96 0.414389183425199330444704413403 2.4131904016758879948172419487 0.883793908892256719022650881123 151 17 27 [31]
97 0.414477238247621300713276853956 2.4126777244220335295630085527 0.885940594094267474584873525610 141 26 23 [31]
98 0.414183953265473536345044897593 2.4143861492360723373071012151 0.886437744097117744735939052952 163 15 29 [31]
99 0.413874238827416963901708644428 2.4161929064084462323520560624 0.886842757278193828853759459731 180 8 36 [31]
100 0.412195412501319769059060798744 2.4260337928840927982523717683 0.881361678454448307830565915161 158 20 36 [31]



Updates

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

31-Mar-2011: First complete presentation from N=1 to N=50.
04-Apr-2011: First improvements for N=27, 28, 30, 32 and 33 by Eckard Specht [31].
05-Apr-2011: Extension up to N=100 by Eckard Specht [31]. All these packings are still far away from the optimum.
06-Apr-2011: Improvements for N=26, 42, 43, 46, 52, 53, 54, 55, 56, 57, 61, 62, 63, 64, 69, 76, 77, 80, 86, 98 and 99 by Eckard Specht [31].
07-Apr-2011: Further improvements for N=44, 71, 77, 78, 79, 81, 84, 89, 91 and 95 by Eckard Specht [31].
09-Apr-2011: More improvements for N=18, 42, 43, 44, 46, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 67, 68, 69, 71, 72, 73, 75, 81, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95 and 96 by Eckard Specht [31].
12-Apr-2011: Improvements for N=26, 32, 41, 43, 53, 55, 57, 64, 65, 66, 80, 81, 82 and 83 by Eckard Specht [31].
14-Apr-2011: Improvements for N=71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 84, 85 and 86 by Eckard Specht [31].
17-Feb-2012: Zhizhong Zeng sent me new record packings for N=17, 18, 19, 21, 22 and 23 [17].
17-Feb-2012: Zhanghua Fu discovered two new record packings for N=14 and 16 [16].
17-Feb-2012: There were some improvements on my hard disk for N=83–97, now they can be seen here [31].
20-Feb-2012: For N=26 there is a better packing in [18] as Fig. 2, but ...
20-Feb-2012: More record packings for N=24, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 47 and 50 by Eckard Specht [31].
20-Feb-2012: Two new record packings for N=24 and 25 by Zhizhong Zeng and Wenqi Huang [17].
20-Feb-2012: ... we can do better [31].
21-Feb-2012: Further improvements for N=28, 29, 30, 31, 32, 34, 35, 37, 38, 42, 43, 44, 45, 46, 48, 49, 50, 52, 53, 55, 56 and 60 by Eckard Specht [31].
22-Feb-2012: Even more improvements for N=28, 29 and 30 by Eckard Specht [31].
23-Feb-2012: Further records for N=23 and 25 by Zhizhong Zeng and Wenqi Huang [17].
27-Feb-2012: One more improvement for N=21 by Zhizhong Zeng and Wenqi Huang [17].
04-Mar-2012: Further improvements for N=26, 27, 28, 29 and 30 by Zhizhong Zeng and Wenqi Huang [17].
04-Mar-2012: The packing for N=27 was only suboptimal and could be improved by Eckard Specht [31].
07-Mar-2012: Again, two improvements for N=26 and 27 by Zhizhong Zeng and Wenqi Huang [17].
08-Mar-2012: Four better packings were found for N=31, 32, 34 and 37 by Eckard Specht [31].
11-Mar-2012: Two new records for N=28 and 29 by Zhizhong Zeng and Wenqi Huang [17].
12-Mar-2012: Only small improvements for N=44, 45, 46, 50 and 52 by Eckard Specht [31].
13-Mar-2012: Again, two new records for N=25 and 30 by Zhizhong Zeng and Wenqi Huang [17].
14-Mar-2012: Due to a mistake, all packings before have had a precision of only 16 decimal places. Now they are provided in full accuracy of 30 digits. Many thanks to David Cantrell who discovered this inaccuracy!
22-Mar-2012: Only small improvements for N=42, 44, 45, 46, 47 and 50 by Eckard Specht [31].
22-Apr-2014: Five new candidates of optimal packings for N=31, 32, 33, 34 and 35 by Zhizhong Zeng, Kun He, Xinguo Yu, Wenqi Huang, and Zhanghua Fu [19].
17-Jul-2014: Two new candidates for N=25 and 30 by Zhizhong Zeng, Kun He, Xinguo Yu, Wenqi Huang, and Zhanghua Fu (their work is partly inspired by Tao Ye et al.) [19].
02-Jun-2024: Significant improvements for N= 20, 26–50 by Jianrong Zhou, Jiyao He, and Kun He [20].

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]   , Feasible Approaches for Solving the Arbitrary Sized Circle Packing Problem, Phd thesis.
[17]   , private communication, February–March 2012.
[18]   Wenqi Huang, Zhizhong Zeng, Ruchu Xu, Zhanghua Fu, Using iterated local search for efficiently packing unequal disks in a larger circle, Advanced Materials Research 430–432 (2012), 1477–1481.
[19]   Zhizhong Zeng, Kun He, Xinguo Yu, Wenqi Huang, Zhanghua Fu, private communication, April-July 2014.
[20]   , 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 ccis, 2005–2024.
[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    02-Jun-2024