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


Last update: 08-May-2013

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
= sqrt(n)/radius; the side length of the square when the greatest circle has radius of 1 is then ratio/sqrt(n)
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.343145750507944321701058056098 4.1213203435651545841924413030 0.554879118756745467857086333956 5 2 D1
3 0.331288928562270941669800278213 5.2282182054315813173364007330 0.632128180990090178970471579195 7 3
4 0.327671056154843250922963844424 6.1036822216637580721153138485 0.702724017943182603210730859003 7 1 3
5 0.323308618073977557636828074220 6.9162028244730783680601885827 0.749814357378836284850371851127 11 5 [16]
6 0.308826772086120924244113994554 7.9315977893652018381146371385 0.734084140258787218872446554323 7 3 3 [16]
7 0.305710487847876555165180746423 8.6544342318222667942051222890 0.761288270073563692844839776847 15 6 [16]
8 0.302700786603807800961876127403 9.3439701841631313343185528936 0.782354522082217983498013426530 13 2 5 [16]
9 0.300483166159275625157192620547 9.9839203585194811337141809948 0.802450477978454556144914491798 17 1 7 [31]
10 0.297724173460773123265662305665 10.6215011814540859155835430178 0.815629140574415321491438636663 15 3 5 [31]
11 0.296004701492537859090239295827 11.2046355131779190958175269246 0.831259066011770166637921479053 17 3 6 [31]
12 0.289837742477757689749518198844 11.9518651556854038159048585551 0.818975689654875047924888441878 25 9 [31]
13 0.287825185416618055544434807717 12.5268790157669354473584668657 0.827661674866360310456390921793 9 9 3 [31]
14 0.285809048868343490593552930349 13.0914587957650970895620747309 0.834437676477867549115172367729 25 2 9 [31]
15 0.283709816855567879051341250502 13.6512137266926730161357476484 0.839083059694806998189737538028 25 3 9 [31]
16 0.281524203539512450047950844074 14.2083698302530708559142624751 0.841766635240215144364638232305 27 3 9 [31]
17 0.279747899942026954775515011574 14.7386472839173845480917181827 0.845639942962773174637616253223 27 4 9 [31]
18 0.277734129428849401651744583720 15.2759068387122558232811183513 0.846971867631332963107167457054 29 4 8 [31]
19 0.276785064191745128681188379745 15.7483170425341476679968609325 0.853860488603508382767334666777 19 10 6 [31]
20 0.274456306321938581436261949167 16.2945279521108136757527296718 0.851385078727847002706831349892 25 8 8 [31]
21 0.273047985611704617305742923123 16.7830415765433006191940775041 0.853823484652278838183849724307 23 10 10 [31]
22 0.271412895743896232323172848964 17.2814771644416923700722921097 0.854147552932873997809432609137 39 3 12 [31]
23 0.269566665039026797206662204871 17.7908923655533900265952606904 0.852492293415287900930305083349 31 8 10 [31]
24 0.268206063254631493888180491049 18.2657298136283546598439278076 0.853324532173647114113367981682 27 11 10 [31]
25 0.266831508356828789936026392958 18.7384167287924505523178728786 0.853547513261358776764432402300 31 10 9 [31]
26 0.266295371576281780917611335140 19.1479839983885747791251412273 0.858689422298192254151788891398 44 4 12 [31]
27 0.265946518336663338977807312138 19.5383359592857184756096464974 0.864670613211773495018782793593 55 15 [31]
28 0.264056409878919174201006378762 20.0392886694733473442321708679 0.860246902824081333920976828924 39 9 13 [31]
29 0.263398267875220807426443727535 20.4449514812116544082024362674 0.863479880281128313688224750783 47 6 14 [31]
30 0.262886232807958488969705233666 21.1778652492794647272987555431 0.866329942566126174774422670451 45 8 14 [31]
31 0.261757467774885724063452130290 21.2706992081747087459271446083 0.866874256863450616753664705524 45 9 12 [31]
32 0.260490173507097893417493918922 21.7161905704694365953074256969 0.865162324662903715278514045933 61 2 13 [31]
33 0.259689290344074244941995097904 22.4526576491607722589660377156 0.856231621890341090730521416304 41 13 10 [31]
34 0.258988039581321295782604010125 22.5143674740283234369669500541 0.867796265821767799510083555057 41 14 9 [31]
35 0.258993130937034173759920297811 23.0324844761688229511267744571 0.873752384136003873151698074246 33 19 8 [31]
36 0.256691933815138579759775560682 23.3743223257519745990440693098 0.864141654685904200945894083835 55 9 17 [31]
37 0.256207663596781235090877730007 23.7415323342731371194288145641 0.866457739387285822505035858651 59 8 14 [31]
38 0.255258908364458417441921008989 24.1496527685480147081135560042 0.865439277179606586615613160273 50 13 11 [31]
39 0.254566773812058302874679580326 24.5318660610020546205381267987 0.865972581493355011616767395051 33 23 10 [31]
40 0.254115863804281920522445799932 24.8884710519091448002867653831 0.867979230617636402631758395086 57 12 14 [31]
41 0.253931263648239075173948283253 25.2159743785818203963763596912 0.871659429803893845873946002721 61 11 14 [31]
42 0.253079301558256649869044595870 25.6075493289061190114723305640 0.870611115089588751104674631002 69 8 18 [31]
43 0.252504425765972892981250473222 25.9695983712074529714369644932 0.871318592295468227421256672149 53 17 13 [31]
44 0.252288709239834124960264526822 26.2922966327391248027405967934 0.874375049759503531427473720360 61 14 17 [31]
45 0.251529317471623888039147771007 26.6696701597302426409554577379 0.873536084556865518652200454046 79 6 19 [31]
46 0.251074458281350817329618232398 27.0132216136787811791188281037 0.874684817971991265437326109777 71 11 16 [31]
47 0.249981561343014599539230208998 27.4246410951341749915661940182 0.871263628963840925111497025983 83 6 20 [31]
48 0.249661263072429203988314652465 27.7504132794327464582265756406 0.873111918573300711102607430015 75 11 15 [31]
49 0.249107933583995149680820681416 28.1002692232337413227698231646 0.873224602361907862313343582315 71 14 15 [31]
50 0.248750603206959162870868041904 28.4263343293222303945427938870 0.874609060516230296559874484857 63 19 15 [31]
51 0.248950250361649567768900664969 28.6861668861780758202723653228 0.879831272507085613323724676426 63 20 13 [31]
52 0.247377421226582238558815923284 29.1502050331720808217003886145 0.872446261966855788721869791616 69 18 17 [31]
53 0.247322464448078594781306879909 29.4357000892464555808767660972 0.875684441212627075596904700951 81 13 17 [31]
54 0.246877254504713575331242156429 29.7656794768309143669040900541 0.876080438828651940708127721188 89 10 21 [31]
55 0.246682346261883923606750614479 30.0637585151523631568889146931 0.878173531872752903254661918842 97 7 18 [31]
56 0.245989156367735342356751864939 30.4213197194388399942296022255 0.876639682402811059314826768826 69 22 17 [31]
57 0.245504728889436767892896078053 30.7522973912790037274995569598 0.876512304319273276029111709776 87 14 19 [31]
58 0.245395598509221020119857593565 31.0346768691528449445453059076 0.878995018543894113288458201855 43 37 10 [31]
59 0.244687796990585490039661185520 31.3916175750783566184903747986 0.877119741019797756868788026728 65 27 13 [31]
60 0.244790910582863512178796589683 31.6431957184580261119345475730 0.880996688207413813859663094547 77 22 17 [31]
61 0.243776487125009798429457367180 32.0385684795188106189620933267 0.876770625166260818430503200456 93 15 21 [31]
62 0.243438644190947899991444410876 32.3449380860739352219215728754 0.877345000705083885123268401149 105 10 25 [31]
63 0.243210934322067420270057874936 32.6352676383416560655393843512 0.878654134562639312917153382104 87 20 18 [31]
64 0.243131294962522515637143986515 32.9040323732410044014364330924 0.880980492681843985696102919960 95 17 21 [31]
65 0.242635009656153292806149433862 33.2279243597786363282501818058 0.880233008021977708363321919497 111 10 24 [31]
66 0.242418592353942602994495755903 33.5124394802135501251131069227 0.881460759735713619273487003447 71 31 17 [31]
67 0.241586597852051833572699669964 33.8816509052461844995398185130 0.878157354237237980803747583675 79 28 15 [31]
68 0.241520243703582538832107746203 34.1429402504746001083915702554 0.880369964653820994418084233625 97 20 22 [31]
69 0.240836164924838390063208056422 34.4907662227814301894753760777 0.878030783358789873789025089654 121 9 22 [31]
70 0.240619947242376206083278887828 34.7710169578118756937421952193 0.879053389943985347983028151402 85 28 16 [31]
71 0.240242141854042207835956594921 35.0735708106509594708147203410 0.878848912894501912448188805670 105 19 21 [31]
72 0.239945394521403770190997343640 35.3633850256567793497781326885 0.879191274254915688510993852724 109 18 24 [31]



Updates

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

08-May-2013: First complete presentation from N=1 to N=72.

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.
[31]   , program csqs, 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