Al Zimmermann's Programming Contest on Circle Packing

Results found by Klaus Nagel and Hugo Pfoertner.

Best configurations found by us

(optimal for N<=18)
N Container Radius Picture Date Time
5 9.0013977460511820 PDF 31-Oct-2005 20:07
6 11.05704039970203 PDF 31-Oct-2005 20:08
7 13.46211068050128 PDF 31-Oct-2005 20:09
8 16.22174667693323 PDF 31-Oct-2005 20:13
9 19.23319390810182 PDF 31-Oct-2005 20:16
10 22.00019301273751 PDF 3-Nov-2005 18:07
11 24.96063429410555 PDF 31-Oct-2005 20:18
12 28.37138944351029 PDF 31-Oct-2005 20:24
13 31.54586701805026 PDF 6-Nov-2005 16:12
14 35.09564717235902 PDF 16-Nov-2005 19:21
15 38.83799552958848 PDF 19-Nov-2005 13:26
16 42.45811646450045 PDF 21-Nov-2005 05:34
17 46.29134213883448 PDF 10-Jan-2006 20:30
18 50.11976266767509 PDF 4-Dec-2006 23:45
19 54.34477610611249 PDF 13-Jan-2006 07:03
20 58.53925193405764 PDF 11-Jan-2006 21:36
21 62.78863608824722 PDF 29-Dec-2005 23:20
22 67.10066181317819 PDF 8-Dec-2005 01:46
23 71.78623954297024 PDF 9-Jan-2006 01:12
24 76.07723259949648 PDF 7-Dec-2005 05:40
25 80.85204359307214 PDF 21-Dec-2005 20:13
26 85.45893414823169 PDF 6-Dec-2005 02:19
27 90.54911646731017 PDF 16-Dec-2005 01:49
28 95.43468060522 PDF 10-Jan-2006 00:31
29 100.483508480917 PDF 22-Nov-2005 03:27
30 105.8130023884226 PDF 9-Jan-2006 22:23
31 110.8652202241489 PDF 28-Dec-2005 20:05
32 116.6314105049203 PDF 01-Jan-2006 18:52
33 122.1227056324939 PDF 28-Dec-05 23:52
34 127.3545271625867 PDF 26-Dec-2005 19:43
35 132.790783827095 PDF 23-Dec-2005 20:16
36 138.8812954720338 PDF 15-Nov-2005 19:41
37 144.8513454030078(*) PDF 24-Dec-2005 07:50
38 150.4595803126423 PDF 12-Jan-2006 06:05
39 155.7749622782255 PDF 28-Dec-05 08:18
40 161.8614076915777 PDF 11-Jan-2006 22:18
41 168.1811947436297 PDF 9-Jan-2006 22:56
42 174.8481963095867 PDF 14-Jan-2006 03:34
43 180.192181180034 PDF 1-Dec-2005 22:40
44 186.5092212838622 PDF 22-Dec-2005 00:25
45 192.7949130742143 PDF 22-Dec-2005 06:44
46 200.1036747130698 PDF 24-Dec-2005 07:54
47 206.385552996902 PDF 21-Dec-2005 19:38
48 213.4327750585821 PDF 3-Jan-2006 01:10
49 220.4752334406955(*) PDF 22-Dec-2005 23:06
50 225.813198821376 PDF 14-Dec-2005 05:51
(*): Konfigurations K37 and K49 were slightly improved during restoration of unavailable submitted files.

A few record configurations found by others:
N Container Radius Picture
19 54.2402935914 PDF
20 58.400567479 PDF
21 62.5588770938 PDF
22 66.7602862414 PDF
23 71.1994617 PDF
26 85.076189788 PDF

Solution quality graph Ratio: (Container Radius)/sqrt(N*(N+1)*(2N+1)/6)

Software

Screen snapshots from Klaus Nagel's Graphical User Interface and Circle Configuration Editor:


Initialisation by Random Spiral.
20 circles, touch points, possible move directions, biggest free space.
24 circles, 40 circles.

Some Fortran Programs written by Hugo:

Create Postscript from Circle Coordinates.
Find free space between inner circles and at boundary (dirty code). Output used to support manual circle editing (especially gap filling).
Example output of cirexc for optimal 18 circles configuration.
Single precision config optimizer, derived from sphere packing program. This program was used to pre-screen the results of Klaus Nagel's batch jobs.
Double precision config optimizer, slow on 32 bit computers. Run for maximum precision.
Target function for all circles. Maximize inverse of container radius.
Target function for one circle. Maximize minimum distance from all neigbors and container.

FMINSI - A Fortran 77 subroutine for unconstrained minimization of a function of N variables

ReadMe, source code, test driver.

Last modification: Feb 19, 2006 by Hugo Pfoertner