Faster Algorithm for Sphere Packing Discovered

← Back to Stories (view on slashdot.org)

Faster Algorithm for Sphere Packing Discovered

Posted by Unknown on Wednesday November 9, 2011 @02:33AM 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.

97 of 134 comments (clear)

Min score:

Reason:

Sort:

Innovation! by Anonymous Coward · 2011-11-09 02:37 · Score: 5, Funny

Scientist finds new innovations while playing with balls. News at 11.
1. Re:Innovation! by underqualified · 2011-11-09 03:34 · Score: 1
  
  But are they the best animal packers in the world? http://www.youtube.com/watch?v=_pApuzdUo-I
Had to be asked. by sgt+scrub · 2011-11-09 02:39 · Score: 4, Funny

Do you really need math to properly pack balls?

--
Having to work for a living is the root of all evil.
1. Re:Had to be asked. by parlancex · 2011-11-09 02:46 · Score: 4, 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.
2. Re:Had to be asked. by Anonymous Coward · 2011-11-09 02:54 · 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.
3. Re:Had to be asked. by BigMike · 2011-11-09 02:56 · Score: 3, Funny
  
  I'm not dumb, but can you provide an example using pancakes?
4. Re:Had to be asked. by tixxit · 2011-11-09 03:00 · Score: 2
  
  Packing spheres
  Spheres or balls, the problem is the same. Given this is about volume, I'd actually say balls is more accurate...
5. Re:Had to be asked. by Flavio · 2011-11-09 03:02 · Score: 2
  
  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.
6. Re:Had to be asked. by Anonymous Coward · 2011-11-09 03:19 · 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
7. Re:Had to be asked. by UnknowingFool · 2011-11-09 03:33 · Score: 4, Informative
  
  Packing spheres has importance when it comes to the chemical industry. Many reactions occur in sphere packed reaction vessels which are analogous to this situation. Most often the spheres are coated with catalysts or are made with catalytic material (ie palladium). Increasing the packing increases the surface area. Two possible benefits are higher yield in terms of either percentage or throughput.
  
  --
  Well, there's spam egg sausage and spam, that's not got much spam in it.
8. Re:Had to be asked. by marcosdumay · 2011-11-09 03:41 · Score: 1
  
  The first time I saw the problem, it was stated as a question. After you formulate your second "right" answer, it stops being obvious.
  
  --
  Rethinking email
9. Re:Had to be asked. by Ibiwan · 2011-11-09 04:29 · Score: 4, Funny
  
  Yes. To simplify the math, assume the pancake is a sphere...
  
  --
  -- //no comment
10. Re:Had to be asked. by mako1138 · 2011-11-09 04:30 · Score: 1
  
  You'll be able to pack more Aebleskiver into your mouth now.
11. Re:Had to be asked. by camperdave · 2011-11-09 04:43 · Score: 1
  
  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.
  
  --
  When our name is on the back of your car, we're behind you all the way!
12. Re:Had to be asked. by tompaulco · 2011-11-09 05:07 · Score: 1
  
  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...
  
  --
  If you are not allowed to question your government then the government has answered your question.
13. Re:Had to be asked. by pnewhook · 2011-11-09 05:20 · Score: 2
  
  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
  Well 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.
  
  --
  Tesla was a genius. Edison however was a overrated hack who liked to torture puppies.
14. Re:Had to be asked. by pnewhook · 2011-11-09 05:21 · Score: 2
  
  You mean meatballs?
  
  --
  Tesla was a genius. Edison however was a overrated hack who liked to torture puppies.
15. Re:Had to be asked. by UnknowingFool · 2011-11-09 05:34 · Score: 1
  
  Theoretically all the scenarios you described are issues. However realistically no process runs at the point of catastrophic failure that would make them very large issues. Most chemical companies would be happy to get 5-10% yield gains because the large volumes that are being produced. 5-10% extra heat at most would not greatly affect most processes with a high safety margin.
  
  --
  Well, there's spam egg sausage and spam, that's not got much spam in it.
16. Re:Had to be asked. by alva_edison · 2011-11-09 05:46 · Score: 1
  
  Only if you want to do it in a reasonable amount of time. If time (or a resource that can be substituted for time, like labor) is not a constraint, then you can brute force it.
  
  --
  He effected a bored affect.
17. Re:Had to be asked. by robthebloke · 2011-11-09 06:03 · Score: 1
  
  Only a limited subset of balls are actually spherical. Using a sphere packing algorithm to determine how many rugby balls to pack into a cylinder is going to give the wrong answer. To add further confusion, some spherical balls can be deflated (soccer balls for example), and some balls (like squash balls) are actually squishy. So i'd say 'spheres' is a more accurate description myself....
18. Re:Had to be asked. by mfnickster · 2011-11-09 06:07 · Score: 1
  
  Packing spheres into any container as efficiently as possible is a deceptively complex problem with a huge variety of applications.
  Unlike turtle stacking, which is NP-hard and completely useless...
  
  --
  "Slow down, Cowboy! It has been 3 years, 7 months and 26 days since you last successfully posted a comment."
19. Re:Had to be asked. by Anonymous Coward · 2011-11-09 06:23 · Score: 1
  
  Mercy me the Slashdot audience is getting dumber.
  Says user 1322105 to user 869860.
20. Re:Had to be asked. by Hentes · 2011-11-09 07:16 · Score: 1
  
  That only depends on the number of mod points handed out.
21. Re:Had to be asked. by excelsior_gr · 2011-11-09 08:31 · Score: 1
  
  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...
22. Re:Had to be asked. by treeves · 2011-11-09 08:41 · Score: 1
  
  You beat me to it. Those things are delicious! I can't believe I'd forgotten about them until this thread prompted my memory.
  
  --
  ...the future crusty old bastards are already drinking the Kool-Aid.
23. Re:Had to be asked. by tixxit · 2011-11-09 09:15 · Score: 1
  
  I mean ball in the mathematical sense, not the rugby sense. A sphere is the boundary of a ball. The ball may (closed) or may not (open) contain the sphere.
24. Re:Had to be asked. by MiniMike · 2011-11-09 09:22 · Score: 1
  
  Just so I can understand it better, can I assume the sphere is shaped like a cow?
25. Re:Had to be asked. by UnknowingFool · 2011-11-09 10:34 · Score: 1
  
  From what I remember random packing is used in cases where structured packing does not offer an advantage. Most often the nature of the reaction is already at the highest possible yield anyways.
  
  --
  Well, there's spam egg sausage and spam, that's not got much spam in it.
26. Re:Had to be asked. by __aaqvdr516 · 2011-11-09 11:47 · Score: 1
  
  Spherical pancakes are called doughnut holes.
  Now, try to find the most efficient way to fit the most doughnut holes inside of your esophagus.
27. Re:Had to be asked. by RivenAleem · 2011-11-10 01:51 · Score: 1
  
  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 ...
Interesting by GameboyRMH · 2011-11-09 02:40 · Score: 2

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
1. Re:Interesting by Anonymous Coward · 2011-11-09 02:55 · 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.
2. Re:Interesting by SomePgmr · 2011-11-09 03:58 · Score: 1
  
  I can't help but wonder how much more crimp there'd be in a previously spent shell if you used this guy's super efficient packing algos.
3. Re:Interesting by ArsenneLupin · 2011-11-09 04:41 · Score: 3, Funny
  
  But wouldn't shaking the cylinder empty the balls?
4. Re:Interesting by lcllam · 2011-11-09 14:25 · Score: 1
  
  If you shake it up and down, yes. Sideways - not so much.
5. Re:Interesting by fishicist · 2011-11-09 23:48 · Score: 1
  
  Add in shaking, and you're essentially describing simulated annealing.
  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? by Bicx · 2011-11-09 02:40 · Score: 1

So if I wanted to efficiently pack small spheres, that would only help me if I stored them in a bunch of long, thin cylinders. I guess if the long, thin cylinders could be packed together efficiently, that wouldn't be an issue.
1. Re:2.7013 times larger at most? by fuzzyfuzzyfungus · 2011-11-09 02:44 · Score: 3, Insightful
  
  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...
2. Re:2.7013 times larger at most? by donscarletti · 2011-11-09 03:38 · Score: 2
  
  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
3. Re:2.7013 times larger at most? by grimJester · 2011-11-09 04:09 · Score: 1
  
  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?
4. Re:2.7013 times larger at most? by grimJester · 2011-11-09 04:11 · Score: 1
  
  After 5 secs of careful thought, I think I've discovered the optimal packing in tubes at most 1 + sqrt(3)/2 sphere diameters wide.
5. Re:2.7013 times larger at most? by Anonymous Coward · 2011-11-09 04:21 · 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.
6. Re:2.7013 times larger at most? by friedmud · 2011-11-09 04:35 · Score: 3, 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 )
  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....
7. Re:2.7013 times larger at most? by khallow · 2011-11-09 05:12 · Score: 1
  
  Pebble bed reactors use spherical fuel pellets.
8. Re:2.7013 times larger at most? by Krishnoid · 2011-11-09 12:51 · Score: 1
  
  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.
The math is even simpler by Anonymous Coward · 2011-11-09 02:45 · Score: 4, Funny

If the diameter of the cylinder is at most 1.0000 times larger than the diameter of the spheres being packed.
1. Re:The math is even simpler by pnewhook · 2011-11-09 05:34 · Score: 1, 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 achieving the theoretical maximum packing density.
  Take that math nerds. Boo yeah.
  
  --
  Tesla was a genius. Edison however was a overrated hack who liked to torture puppies.
2. Re:The math is even simpler by God+Of+Atheism · 2011-11-09 07:41 · 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
3. Re:The math is even simpler by pnewhook · 2011-11-09 09:08 · Score: 1
  
  But I bet I still get higher density than the mathematical solution.. Besides, metals expand by maybe 0.2% of volume when melted so the impact is insignificant.
  
  --
  Tesla was a genius. Edison however was a overrated hack who liked to torture puppies.
2.7013 Times by Aladrin · 2011-11-09 02:46 · Score: 1

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

--
"If you make people think they're thinking, they'll love you; But if you really make them think, they'll hate you." - DM
1. Re:2.7013 Times by hosecoat · 2011-11-09 03:01 · Score: 1
  
  good thing my cylindrical display is only 2.5 times as large as its spherical pixels
2. Re:2.7013 Times by canajin56 · 2011-11-09 07:36 · Score: 1
  
  lim_{x->infinity} x/(x+1) = 1, so asymptotically there's no difference between the two phrases ;) This is also a great justification for ignoring off-by-one errors of all sorts!
  
  --
  ASCII stupid question, get a stupid ANSI
Great, but... by JustinFreid · 2011-11-09 02:47 · Score: 1

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

--
Hey, how's it going?
1. Re:Great, but... by Hentes · 2011-11-09 03:34 · Score: 1
  
  Packing cylinders into cuboids can be reduced to packing circles in rectangles, which is already solved.
2. Re:Great, but... by ewanm89 · 2011-11-09 12:27 · Score: 1
  
  Assuming all cylinders have the same diameter it is called hexagonal packing.
For those of you wondering by Chrisq · 2011-11-09 02:51 · Score: 1

the 2.7013 is an approximation of 1+1/sin(/5)
1. Re:For those of you wondering by Chrisq · 2011-11-09 02:52 · Score: 5, Informative
  
  Sod the slashdor character filter .. thats 1+1/sin(Pi/5)
2. Re:For those of you wondering by DriedClexler · 2011-11-09 04:05 · Score: 1
  
  I think you mean (+ 1 (/ 1 (sin (/ Pi 5) ) ) ).
  Some of us prefer Lisp notation, ya know.
  
  --
  Information theory is life. The rest is just the KL divergence.
3. Re:For those of you wondering by hey! · 2011-11-09 04:27 · Score: 2
  
  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.
4. Re:For those of you wondering by GuldKalle · 2011-11-09 05:11 · Score: 1
  
  I don't think "I think you mean" means what you think "I think you mean" means...
  
  --
  What?
5. Re:For those of you wondering by pnewhook · 2011-11-09 05:29 · Score: 4, 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.
  
  --
  Tesla was a genius. Edison however was a overrated hack who liked to torture puppies.
6. Re:For those of you wondering by Lexx+Greatrex · 2011-11-09 06:45 · 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.
7. Re:For those of you wondering by garyebickford · 2011-11-09 09:34 · Score: 1
  
  Thanks. I now have a new email sig. :D
  
  --
  It's easier to be a result of the past, but more fun to be a cause of the future! http://www.spacefinancegroup.com/
8. Re:For those of you wondering by DriedClexler · 2011-11-09 10:53 · Score: 1
  
  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
  
  (define (doesntmean x) (concat "I don't think" x "means what you think" x "means"))
  
  to mock what you had just done, and I figured I might was well apply it again.
  
  --
  Information theory is life. The rest is just the KL divergence.
More Applications by Thelasko · 2011-11-09 02:54 · Score: 1

Sphere packing is related to all crystalline structures, not just liquid crystals. This could have a profound impact on material science, as a whole.

--
One of our competitors trademarked the term "hypothesis". From now on, we will call them "boneheaded ideas".
1. Re:More Applications by Chrisq · 2011-11-09 03:02 · Score: 2
  
  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.
Major reasons we care about sphere packing by JoshuaZ · 2011-11-09 02:55 · 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 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.
1. Re:Major reasons we care about sphere packing by martas · 2011-11-09 04:05 · Score: 2
  
  As a statistician, I know about the theoretical importance of packing numbers. You mention that packings come up in error correcting codes, and I can certainly see why. But from what you said I infer that they are not just used for theoretical analysis, but to actually design codes. Is this true? I don't know much about error correcting codes, but in estimation problems packing/covering arguments are typically used only in theory to establish upper/lower bounds, because there are often much simpler estimators that don't use them explicitly, i.e. even if we could get exact packings/coverings of a space, we would probably not use them in practice for several reasons. Is this not the case in coding?
  
  --
  weinersmith
2. Re:Major reasons we care about sphere packing by JoshuaZ · 2011-11-09 04:38 · Score: 1
  
  The error coding end of this sort of thing is farther from the sort of work I've done so I'm not sure I can answer the question in detail. It is the case certainly that in limited contexts where the packing is really easy to understand (like the packing one gets from the leech lattice) that they are actively used in code design. I don't know how much they are used for higher dimensional cases in practice, especially because one isn't generally getting much better than a simple lattice packing and the technical complexity can make practical implication difficult.
3. Re:Major reasons we care about sphere packing by khallow · 2011-11-09 05:10 · Score: 1
  
  In error correcting codes, you only need to get the packing once and then hard code it into whatever software/hardware you're using. I must admit that I don't see much point to having a lot of bins (the "spheres") however in the code. A few bins with a high data rate seems more useful (but maybe that's all played out now).
  
  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 related but not identical to the sphere packing problem.
4. Re:Major reasons we care about sphere packing by martas · 2011-11-09 05:24 · Score: 1
  
  Huh, this is the first I'm hearing of the "kissing problem" (nice name!). I'm guessing it comes up because contacts represent the areas of uncertainty?
  
  --
  weinersmith
5. Re:Major reasons we care about sphere packing by khallow · 2011-11-09 05:58 · Score: 1
  
  I see it as more useful for error correcting systems that can change continuously in state. With a lot of bins, your state might run though a number of bins to reach its destination bin. OTOH, if all those states "kiss" a central region (which is similar in size to the bins), then you'll get a lot less bin crossings.
6. Re:Major reasons we care about sphere packing by Rumagent · 2011-11-09 06:03 · Score: 1
  
  Not to mention that it is also cool. This is news for nerds after all:)
7. Re:Major reasons we care about sphere packing by EnsilZah · 2011-11-09 08:49 · Score: 1
  
  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 by Chrisq · 2011-11-09 02:55 · Score: 1

Densest columnar structures of hard spheres from sequential deposition
What could possibly go wrong... by Maximum+Prophet · 2011-11-09 03:07 · Score: 1

This is how Ice Nine was discovered in Kurt Vonnegut's, "Cat's Cradle"...

--
All ideas^H^H^H^H^Hprocesses in this post are Patent Pending. (as well as the process of patenting all postings)
Think Slashdot isn't news for nerds anymore? by bzipitidoo · 2011-11-09 03:20 · Score: 1

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 technologies could ever plausibly be built, we strongly suspect many of them are just flat impossible, but we've gotten so used to seeing them in SF we hardly even notice. Our brave heroes have 1 hour to save the ship, planet, or galaxy from certain doom, and they always succeed, always hit on the right answer just in time. Sure, scientists want those kinds of answers too. But we understand it's not that easy. The public really doesn't.

--
Intellectual Property is a monopolistic, selfish, and defective concept. It is "tyranny over the mind of man"
1. Re:Think Slashdot isn't news for nerds anymore? by CrimsonAvenger · 2011-11-09 04:16 · Score: 1
  
  Sure, scientists want those kinds of answers too. But we understand it's not that easy. The public really doesn't.
  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.
  
  --
  
  "I do not agree with what you say, but I will defend to the death your right to say it"
2. Re:Think Slashdot isn't news for nerds anymore? by friedmud · 2011-11-09 04:25 · Score: 1
  
  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 trolls seem to have left Slashdot. Maybe we can actually refocus it on niche news of interest to scientists and nerds in general...
I hear that by Boawk · 2011-11-09 03:45 · Score: 1

this research was funded by a grant from Hanes.
This should be useful in physics by jmv · 2011-11-09 03:52 · Score: 1

Considering a spherical horse in simple harmonic motion...

--
Opus: the Swiss army knife of audio codec
I was excited until... by friedmud · 2011-11-09 04:13 · Score: 1

"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
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....
1. Re:I was excited until... by bityz · 2011-11-09 07:50 · Score: 1
  
  Totally a guess by a layperson....
  <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.
  </naive>
2. Re:I was excited until... by bityz · 2011-11-09 08:40 · Score: 1
  
  Sorry for replying to my own comment... I should have put some context into that previous comment. I was responding to the implication that friedmud was hoping for a generalization to sphere packing in cylinders with a less restrictive constraint on the ratio of the diameters. I gave my naive guess as to how that generalization might be found. (I felt compelled to clarify despite that this comment is buried so low no-one will ever see it :) )
the only caveat being it works for a spherical... by mapkinase · 2011-11-09 05:04 · Score: 1

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
..and the spheres need to be in vacuum.

--
I do not believe in karma. "Funny"=-6. Do good and forbid evil. Yours, Oft-Offtopic Flamebaiting Troll.
A level up on the problem by Twinbee · 2011-11-09 05:13 · Score: 1

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

--
Why OpalCalc is the best Windows calc
One step closer to P = NP? by L473ncy · 2011-11-09 05:22 · Score: 1

So does this mean that we're one step closer to solving P = NP?
1. Re:One step closer to P = NP? by JoshuaZ · 2011-11-09 05:46 · Score: 1
  
  Not really. There are connected problems involving finding information about lattices that are in general NP-complete (in particular, given an explicit lattice in k dimensions, finding the shortest non-zero vector in the lattice is NP-complete. One needs to be careful here to turn this into a decision problem from a function problem but this is a technical detail. But those problems are in arbitrarily many dimensions and don't in any obvious way get easier when one can pack spheres efficiently. (Instead if one had efficient ways of solving those problems one could possibly pack spheres more efficiently. For low dimensions we can solve the lattice problem efficiently, and the general belief is that in high dimensions the best packings will not necessarily be lattice packings. There are a few other packing problems that are NP hard or NP complete (see e.g. http://dx.doi.org/10.1023/A:1009831621621 ) but this is a much more general problem. Moreover, it isn't at all clear that this procedure even gives much better asymptotic behavior for the narrow problem in question (although it probably does). So overall, this really doesn't impact P ?=NP issues much at all.
Re:Too late by JoshuaZ · 2011-11-09 05:51 · Score: 1

For three-dimensions for a large object where the balls are small compared to the volume that contains them, a close approximation of Kepler's packing will be near optimal. http://en.wikipedia.org/wiki/Kepler's_conjecture. So one can assume that around 74% of the volume of the drum will be filled, and divide that by the volume of a golfball and you should get an answer that is correct within 5% or so. It will probably be a slight overestimate of how many you can fit in.
Gum Balls by Nom+du+Keyboard · 2011-11-09 06:02 · Score: 1

Real-world application: Will this help me in the guess the number of gum balls in the container contests?

--
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
1. Re:Gum Balls by Gibgezr · 2011-11-09 07:29 · Score: 1
  
  Not unless they use very large gumballs and a very narrow cylindrical bottle.
2. Re:Gum Balls by Hentes · 2011-11-09 07:29 · Score: 1
  
  No, but this will.
Re:Too late by PPH · 2011-11-09 08:24 · Score: 1

... or how many balls will fit in your girlfriend's mouth?

--
Have gnu, will travel.
Amazing by BattleApple · 2011-11-09 08:52 · Score: 1

I was just able to get FIVE tennis balls into a container that usually holds three after applying this algorithm.
Oh Dammnit! by lcllam · 2011-11-09 14:19 · Score: 1

D(c)/D(s) = 2.7014. I'll stick to the old fashioned way, then...
Not the greatest party topic by phatsonic · 2011-11-09 21:48 · 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? by ThomasCR · 2011-11-12 02:15 · Score: 1

http://www.algit.eu/index.php?option=com_content&view=article&id=71&Itemid=86 Download and play.