Slashdot Mirror
Faster Algorithm for Sphere Packing Discovered
sciencehabit writes with an article in Science about a new way to pack spheres into a cylinder. From the article: "One day, physicist Ho-Kei Chan of Trinity College Dublin was playing with steel ball bearings, trying to pack them into a little cylindrical tube in the most efficient way possible. It's a tricky problem that can take even a powerful computer a week to calculate. But after thinking about it for a while, Chan has figured out a way to simplify the math. The advance could help engineers pack all sorts of spheres more efficiently, from nano-sized buckyballs to Christmas tree ornaments. Another potential application is liquid crystal displays such as those used in televisions and computer monitors. If scientists could make liquid crystal molecules obey these rules, they could potentially create a whole new class of liquid crystals."
One caveat is that the diameter of the cylinder can be at most 2.7013 times as large as the diameter of the spheres being packed.
Scientist finds new innovations while playing with balls. News at 11.
Do you really need math to properly pack balls?
Having to work for a living is the root of all evil.
I always thought the most efficient way was to choose a container and then let gravity do the work. Not math involved and I bet it's only slightly less efficient :-P
"When information is power, privacy is freedom" - Jah-Wren Ryel
I'm sure that this work will have no applications to the design of future nuclear fuel rod assemblies, which bear no relationship whatsoever with closely packed fuel pellets inside an array of thin cylinders...
If the diameter of the cylinder is at most 1.0000 times larger than the diameter of the spheres being packed.
Sod the slashdor character filter .. thats 1+1/sin(Pi/5)
The summary doesn't mention one of the main reasons we care about sphere packing. If one is interested in error correcting codes then the best way of thinking about how many messages one can reliably send is a function of how efficiently you can pack sphere. The essential idea is that you think of your signal space as some large dimensional space, and you then consider your potential error to be the radius of the spheres. Then if you can find a decent packing of the spheres and you send as your messages the signals contained as the center of the spheres then you have a more efficient ability to send messages reliably with minimal chance of error. It seems that most of the work discussed in TFA is essentially for three dimensions only so this major reason people care about sphere packing (indeed probably the biggest reason) isn't that deeply connected.
In general sphere packing shows up in a lot of contexts and is pretty tough. For high dimensions we can't generally do much more than a random packing, although there are exceptions. For example, in 24 dimensions one has the very elegant Leech lattice http://en.wikipedia.org/wiki/Leech_lattice which allows a very regular, very efficient packing of spheres, and leads to the Golay code http://en.wikipedia.org/wiki/Binary_Golay_code which is a very efficient code for sending reliable signals and is not that hard to actually implement in practice since the math behind is straightforward.
One related issue is showing that a given type of sphere packing is the best possible. This turns out to be really, really tough. Kepler (yes, that Kepler, he did a lot.) famously conjectured that for spheres in three-dimensions the most efficient pacing was in general the obvious packing (the packing one sees with oranges in a grocery store). http://en.wikipedia.org/wiki/Kepler_conjecture. This problem wasn't solved until 1998, which made it for a long time one of the oldest unsolved problems in mathematics. Even just getting weak lower bounds is tough, especially in the higher dimensional case. The range between the upper and lower bounds is generally massive, because it is tricky to actually figure out good ways of fitting spheres together and it is really tricky to show that there isn't some clever way of getting more spheres in. (The earlier mentioned Leech lattice essentially works because it turns out that if one makes the essentially obvious lattice in 24 dimensions you can just manage to then slip a few more spheres in.) Last semester I was doing work related to what is called the Jordan-Schur theorem http://en.wikipedia.org/wiki/Jordan-Schur_Theorem, and it turned out that one might be able to improve some of the bounds if one had decent sphere packing lower bounds. Unfortunately, for my purposes none of the sphere packing results known were almost any better than just the naive volume estimates (that is, that you can't fit more little spheres into a region than you have volume). In high dimensions, things are just that bad.
TFA is actually talking about a special where you want to fit your spheres in a region of a specific shape, in this case, a cylinder. Things like this show up fairly frequently. In the case I was working with, one needed to fit the spheres around a larger sphere. Chan's result is quite interesting, although it looks to some extent like how well his type of packing works is empirical. The paper doesn't seem to be giving much in the way of direct upper bounds on how well the packing will work in general, although for many applied purposes his method should work well enough. I suspect that over the next few months people will be looking at his method, generalizing it, and trying to use it to establish explicit, non-computational, upper bounds.
Sphere packing is related to all crystalline structures, not just liquid crystals. This could have a profound impact on material science, as a whole.
I think this will be limited by the constraint on the maximum diameter, which will exclude most crystalline substances. It could have an impact on monomolecular wires though.
It is basically a greedy algorithm that scans along the length of the cylinder
When you add a ball, you can work out where the possible positions of the next ball touching it, the side of the tube and an adjacent ball and repeat for that position, to give a spiral.
Like many greedy algorithms, this solution only works for a very constrained subset of the problem. 2.7013 is the diameter where it fails to be optimal, and packing efficiency degrades pretty horrifically after that. I would have used a greedy algorithm that simply places balls in the lowest position available that touches another ball (a priority queue can be used, when you place a ball, add the possible positions of the next ball to the queue, queued by height). This approach could be made to perform the same optimal packing in a narrow tube, by starting against the edge and would degrade to a suboptimal but decent approximation beyond that.
I'm looking at this and can't help but thinking that if I designed an algorithm like that, it would have caused a major glitch and everyone would be mad at me. If he were a programmer, Mr Chan would get a quick lecture from the lead about testing better before committing his code. I guess physicists get a photo shoot and a puff piece for the same achievement, but we cannot be all held to the same standard.
When Argumentum ad Hominem falls short, try Argumentum ad Matrem
I find it kind of spooky that sqrt(5) appears in the formula for the golden ratio and in the closed expression formula to calculate Fibonacci numbers, and here we have it again. Oh, I can do the calculations for the eigenvalues of the Fibonacci matrix and arrive at the closed formula, it's just surprising to see sqrt(5) pop up. I suppose I should expect some irrational number expressed as a power of some rational number to pop up, but 5 seems like such an innocuous number. So far as I know sqrt(3) and sqrt(7) don't have this gatecrashing habit.
You almost couldn't pick a more innocuous looking number than 5. Of course the sqrt(2) shows up all the time, but that makes sense because of our way of seeing things in dualities and halves. If we define pi in terms of the diameter of a circle but define the circle itself in terms of its radius, we pretty much force ourselves to deal with factors of two. But the sqrt(5) thing is like some cosmic trickster looked at the succeeding prime numbers and thought, "Three comes right after two so it's too obvious; seven is too obviously non-obvious; I think I'll go with five."
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.
Right line of thinking... but wrong application.
Traditional Light Water Reactors (LWRs) using "fuel rods" use cylindrical fuel (called pellets) stacked perfectly on top of each other inside a tube (the "rod") that is just barely large enough to admit the pellets. So this wouldn't apply there...
(If you would like to see _me_ explaining some simulations of nuclear fuel rods (among other things) check out this youtube video: http://www.youtube.com/watch?v=V-2VfET8SNw )
However, as I mentioned in a comment below, this _does_ have applications to generating geometry and meshes for simulations of pebble bed reactors (PBRs) http://en.wikipedia.org/wiki/Pebble_bed_reactor
EXCEPT: PBRs definitely don't qualify for the 2.7013 restriction....
I suppose I should expect some irrational number expressed as a power of some rational number to pop up, but 5 seems like such an innocuous number
Because 5 is the number of points on a pentagram which is the sign of the devil. Any math with 5 or sqrt(5) should be avoided at all costs lest the devil take your soul and you are then stuck being an accountant.
Tesla was a genius. Edison however was a overrated hack who liked to torture puppies.