Faster Algorithm for Sphere Packing Discovered 134
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.
Re:Had to be asked. (Score:5, Informative)
Mercy me the Slashdot audience is getting dumber. Packing spheres into any container as efficiently as possible is a deceptively complex problem with a huge variety of applications.
For me personally working in computer graphics, packing spheres as tightly as possible into other spheres has practical application in computing efficient bounding volume hierarchies as an acceleration structure for efficient ray tracing.
This deals with packing spheres into a cylinder so it is a different subset of the same problem, but it is still interesting and useful.
Re:For those of you wondering (Score:5, Informative)
Major reasons we care about sphere packing (Score:5, Informative)
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 [wikipedia.org] which allows a very regular, very efficient packing of spheres, and leads to the Golay code http://en.wikipedia.org/wiki/Binary_Golay_code [wikipedia.org] 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 [wikipedia.org]. 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 [wikipedia.org], 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.
Re:Had to be asked. (Score:3, Informative)
Ironically, packing spheres bears no relation to creating bounding volume hierarchies, since you can't cover 3D space with sphere packing so bounding sphere hierarchies invariably involve overlapping spheres. The sphere packing problem means no overlapping. You're probably thinking about finding the minimum bounding sphere for a mesh, which is a completely different problem (disclaimer: I work in CG too).
Sheesh, is the Slashdot audience getting dumber or something? :p
Re:Had to be asked. (Score:5, Informative)
Re:2.7013 times larger at most? (Score:4, Informative)
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 [youtube.com] )
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 [wikipedia.org]
EXCEPT: PBRs definitely don't qualify for the 2.7013 restriction....