## Faster Algorithm for Sphere Packing Discovered 134

Posted
by
Unknown Lamer

from the one-thousand-clown-bearings dept.

from the one-thousand-clown-bearings dept.

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.
## Innovation! (Score:5, Funny)

Scientist finds new innovations while playing with balls. News at 11.

## Re: (Score:2)

## Had to be asked. (Score:5, Funny)

Do you really need math to properly pack balls?

## Re:Had to be asked. (Score:5, Informative)

Mercy me the Slashdot audience is getting dumber. Packing

spheresinto 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:Had to be asked. (Score:5, Interesting)

Another application is in computing the capacity of a noisy communication channel (that is, the maximum rate of reliable information flow) in information theory.

## Re: (Score:2)

Another application is in computing the capacity of a noisy communication channel (that is, the maximum rate of reliable information flow) in information theory.

That's easy: Number of +5 insightful posts/total number of posts on any particular Slashdot story.

## Re: (Score:2)

That only depends on the number of mod points handed out.

## Re: (Score:3, Funny)

I'm not dumb, but can you provide an example using pancakes?

## Re:Had to be asked. (Score:5, Funny)

## Re: (Score:2)

Just so I can understand it better, can I assume the sphere is shaped like a cow?

## Re: (Score:2)

Spherical pancakes are called doughnut holes.

Now, try to find the most efficient way to fit the most doughnut holes inside of your esophagus.

## Re: (Score:2)

You'll be able to pack more Aebleskiver [wikipedia.org] into your mouth now.

## Re: (Score:2)

You beat me to it. Those things are delicious! I can't believe I'd forgotten about them until this thread prompted my memory.

## Re: (Score:2)

I'm not dumb, but can you provide an example using pancakes?No, it just wouldn't work. However we can use cows. Assume spherical cows of uniform density...

## Re: (Score:3)

## Re: (Score:3)

Packing

spheresSpheres or balls, the problem is the same. Given this is about volume, I'd actually say balls is more accurate...

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:3)

Mercy me the Slashdot audience is getting dumber.While the Slashdot audience isn't as geeky as it was 10 years ago, this is a perfectly legitimate question that everyone (even you, the Great Ball Packer) has asked upon first seeing this problem.

Also, while fast sphere packing algorithms are of practical interest, I think your involvement with this problem makes you overestimate their importance.

## Re:Had to be asked. (Score:5, Informative)

## Re: (Score:2)

Yes, but in such cases the column is randomly packed (by just throwing the catalyst pearls in the cylinder), not using an algorithm. Nor can you even apply an algorithm for that matter...

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2)

The first time I saw the problem, it was stated as a question. After you formulate your second "right" answer, it stops being obvious.

## Re: (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

probablythinking about finding the minimum bounding sphere for a mesh, which is acompletelydifferent problem (disclaimer: I work in CG too).Sheesh, is the Slashdot audience getting dumber or something? :p

## Re: (Score:3)

For me personally working in computer graphics,

packing spheres as tightly as possible into other sphereshas practical application in computing efficient bounding volume hierarchies as an acceleration structure for efficient ray tracingWell that's easy - just put them all at the same origin. That way they overlap like an onion and occupy only the volume of the largest sphere. Duh.

## Re: (Score:2)

Unlike turtle stacking, which is NP-hard and completely useless...

## Re: (Score:1)

Mercy me the Slashdot audience is getting dumber.

Says user 1322105 to user 869860.

## Re: (Score:2)

It also has great applications for the Internet, and making use of all the available bandwidth. If you think of the information at spherical packets, and the Internet as a series of tubes ...

## Re: (Score:2)

## Interesting (Score:3)

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

## Re: (Score:1)

... let gravity do the work.

Naw dude, everyone knows you got to shake the cylinder really hard to make the little balls pack themselves in nice and tight. Fill - Shake - Top Off - Shake - Top Off - Shake - etc. until you can't get any more in the tube.

## Re:Interesting (Score:4, Funny)

## Re: (Score:1)

## Re: (Score:2)

## Re: (Score:1)

Without the shaking, you'll quickly converge to a local minimum. With shaking, you explore the possibilities nearby and, provided you shake it just right, you eventually converge on the global minimum.

Simulated annealing is a really common approach when you have lots and lots of variables; in this example, the free parameters are the locations of each of the spheres. The authors even use this in their paper as a check.

## 2.7013 times larger at most? (Score:2)

## Re:2.7013 times larger at most? (Score:4, Insightful)

## Re: (Score:1)

What future nuclear fuel rods? Nuclear fuel runs out before even oil runs out, and with solar and wind *already* being cheaper, renewable and a lot better for the environment, the only point left would be to use it in spacecrafts and some scientific applications.

## 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....

## Re: (Score:2)

## Re: (Score:3)

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 alg

## Re: (Score:2)

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.

Wouldn't this reduce to a 2d problem where you just go left-right-left-right? Place one ball against the wall of your narrow tube, two others touching that ball and the opposite side of the tube and so on?

## Re: (Score:2)

## Re: (Score:2)

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.

Well, duh [xkcd.com].

## The math is even simpler (Score:4, Funny)

If the diameter of the cylinder is at most 1.0000 times larger than the diameter of the spheres being packed.

## Re: (Score:2, Funny)

The math gets really simple if you solve it as an Engineer. The highest packing efficiency and theoretical maximum density can be clearly shown to be achieved if the volume of the spheres added is equal to the volume of the container itself. This can be shown for any number of spheres of any diameter and any size container, assuming no one sphere is bigger than the container itself. The practical engineering solution then gets applied by heating the container so the spheres melt and form a liquid, thus a

## Re: (Score:1)

But most materials (when keeping pressure equal) expand when melting. Thus if you have one sphere made out of such a material and one container of equal size, the melted sphere won't fit into the container

## Re: (Score:2)

## 2.7013 Times (Score:2)

Not 2.7013 time larger. 2.7013 times as large. It's a massive difference.

## Re: (Score:1)

## Re: (Score:2)

## Great, but... (Score:1)

When is he going to develop an algorithm to determine the most efficient way to pack cylinders into rectangular (cuboid) shipping containers?

## Re: (Score:2)

Packing cylinders into cuboids can be reduced to packing circles in rectangles, which is already solved.

## Re: (Score:2)

## For those of you wondering (Score:2)

## Re:For those of you wondering (Score:5, Informative)

## Re: (Score:2)

I think you mean (+ 1 (/ 1 (sin (/ Pi 5) ) ) ).

Some of us prefer Lisp notation, ya know.

## Re: (Score:2)

I don't think "I think you mean" means what you think "I think you mean" means...

## Re: (Score:2)

Thanks. I now have a new email sig. :D

## Re: (Score:2)

I don't think "I don't think "I think you mean" means what you think "I think you mean" means" means what you think "I don't think "I think you mean" means what you think "I think you mean" means" means ...

Sorry, I had just written the function

to mock what you had just done, and I figured I might was well apply it again.

## Re: (Score:3)

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

## Re:For those of you wondering (Score:5, Funny)

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.

## Re: (Score:1)

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... You almost couldn't pick a more innocuous looking number than 5... But the sqrt(5) thing is like some cosmic trickster looked at the succeeding prime numbers...

The only thing I find spooky is the anthropomorphisation of mathematical formula.

## More Applications (Score:2)

## Re: (Score:3)

Sphere packing is related to all crystalline structures, [wikipedia.org] 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.

## 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: (Score:3)

## Re: (Score:2)

## Re: (Score:2)

Also, the bins don't tend to be sphere shaped, especially for digital codes.

Finally, I think the more interesting problem here is the kissing problem which happens to be closely rela

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2)

Not to mention that it is also cool. This is news for nerds after all:)

## Re: (Score:2)

Did you use your packing knowledge to pack this post so it triggers 'Read the rest of this comment...' while still being readable in its entirety without clicking it?

## See this (Score:2)

## What could possibly go wrong... (Score:2)

## Think Slashdot isn't news for nerds anymore? (Score:2)

Then take this!

I'd like to see even more.

And note this is a very nuanced result. It's not the optimum answer to all cases of the sphere packing problem, complete with proof of optimality. It is only a fast way to find a good answer in some cases. So many people expect such absolute, complete, and progressive answers from science. The media likes to spin things that way. Science fiction is full of such fantastically powerful technology that it warps expectations. We have no idea how some of these t

## Re: (Score:2)

Yes, actually the public really does. Most, if not all, of the public can tell the difference between "science fiction" and "science" with not trouble.

And very few of the public are really wasting a lot of lifespan waiting on scientists to solve their problems.

## Re: (Score:2)

I completely agree...

This is how science is done. It's a _ton_ of tiny small steps towards an eventual achievement that will have broader impact on society as a whole.

The fact that the media only latches on to the end-goal achievements gives a false sense of "magic" about science and leads to the average person believing that "scientists just get lucky"... and that it really isn't "hard" to achieve these things....

I too would love to see more of these types of stories on Slashdot... a lot of the typical tr

## I hear that (Score:1)

## This should be useful in physics (Score:2)

Considering a spherical horse in simple harmonic motion...

## I was excited until... (Score:2)

"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."

Around here we need a fast packing algorithm for generating geometry for simulations of Pebble Bed Reactors http://en.wikipedia.org/wiki/Pebble_bed_reactor [wikipedia.org]

We have quite a bit of code to do these problems... and we never actually end up computing perfect packing... we just hope to get close....

Maybe someone will see a way to extend this to more general ball packing problems....

## Re: (Score:1)

<naive>it seems that the algorithm depends upon the analogy with a flat two dimensional disk packing problem and this leads to the bound in the ratio of the diameters. I would guess that it would be possible to generalize to a cylindrical annulus with limits on the distance between the inner and outer cylinders. Then the problem becomes (approximately) analogous to optimally vertically stacking planes of packed spheres as you continue to pack in smaller annuli.

## Re: (Score:1)

## the only caveat being it works for a spherical... (Score:2)

## A level up on the problem (Score:2)

A while back, I created a much more devious, twisted version of the sphere packing problem which can be found here:

http://www.skytopia.com/project/imath/imath.html#12 [skytopia.com]

## One step closer to P = NP? (Score:1)

## Re: (Score:2)

## Gum Balls (Score:2)

## Re: (Score:1)

## Re: (Score:2)

No, but this [wikipedia.org] will.

## Amazing (Score:2)

## Oh Dammnit! (Score:1)

## Not the greatest party topic (Score:1)

- Hey, I heard you won a big prize for your latest paper! That's so cool. What was it about?

- Packing spheres into a cylinder.

- Ahem... I think I'll go somewhere else now...

## Want to pack yourself? (Score:1)

## Re: (Score:2)

## Re: (Score:2)