[math-fun] Packing squares in circles
I've been playing around with packing things, and ran across Erich Friedman's site: http://www.stetson.edu/~efriedma/packing.html I wrote a program to pack unit squares into circles: http://lunkwill.org/src/square-in-circle/ It even generates SVG images of the smallest circles it can find that support a given number of squares (svg is neat!). They're in the svg/ directory, but my browser doesn't like to display them, so I converted them into .PNGs as well. An interesting integer sequence might be the number of unit squares that pack into circles of increasing integer radii. My program gives that sequence as the following for circles of r=1..19: 0,8,21,40,65,97,135,180,229,286,350,419,495,575,664,761,860,966,1079 (but it might be off by a few). -J
----- Original Message ----- From: "Jason Holt" <jason@lunkwill.org> To: <math-fun@mailman.xmission.com> Sent: Friday, November 10, 2006 09:48 Subject: [math-fun] Packing squares in circles
I've been playing around with packing things, and ran across Erich Friedman's site: http://www.stetson.edu/~efriedma/packing.html
I wrote a program to pack unit squares into circles: http://lunkwill.org/src/square-in-circle/
It even generates SVG images of the smallest circles it can find that support a given number of squares (svg is neat!). They're in the svg/ directory, but my browser doesn't like to display them, so I converted them into .PNGs as well.
I suppose that you've only considered packings in which all squares have the same orientation (i.e., none are slanted wrt others). Perhaps there's a not-too-distant relation to the problem of the number of lattice points in a circle: http://mathworld.wolfram.com/GausssCircleProblem.html. Anyway, if anyone can improve some of the packings shown on Erich's page, he and I would certainly be interested.
An interesting integer sequence might be the number of unit squares that pack into circles of increasing integer radii. My program gives that sequence as the following for circles of r=1..19:
0,8,21,40,65,97,135,180,229,286,350,419,495,575,664,761,860,966,1079
(but it might be off by a few).
Well, the sequence should begin with 1, rather than 0. ;-) FWIW, a crude approximation is given by floor(pi r^2 - 2.9 r + 1.5). For r = 1..19, that approximation yields 1,8,21,40,65,97,135,179,229,286,349,419,494,576,664,759,860,967,1080. David W. Cantrell
On Fri, 10 Nov 2006, David W. Cantrell wrote:
Anyway, if anyone can improve some of the packings shown on Erich's page, he and I would certainly be interested.
I tweaked the program to recursively search for the minimum r that supports a number of squares (in my parallel-row form): http://lunkwill.org/src/square-in-circle/ Graphics in: http://lunkwill.org/src/square-in-circle/svg-minimum-r/ (David's quadratic approximation comes in handy there - thanks!) Interestingly, for n=5..35, my algorithm is usually within 5% of the tilted solutions. n=35 is actually one of the biggest differences: Eppstein got 3.640 vs my 3.760. n=11 seems to almost not exist at all in row-parallel form: my algorithm stops trying at a delta r of 1e-7, and for n=11 gave up at r=2.236068, where it actually fit 12 squares.
participants (2)
-
David W. Cantrell -
Jason Holt