Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Math Science

Faster Algorithm for Sphere Packing Discovered 134

Posted by Unknown Lamer 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.
This discussion has been archived. No new comments can be posted.

Faster Algorithm for Sphere Packing Discovered More

Faster Algorithm for Sphere Packing Discovered

Comments Filter:

  • Innovation! (Score:5, Funny)

    by Anonymous Coward on Wednesday November 09, 2011 @10:37AM (#37998996)

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

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

    by sgt scrub ( 869860 ) <saintium@NOSpAM.yahoo.com> on Wednesday November 09, 2011 @10:39AM (#37999032)

    Do you really need math to properly pack balls?

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

      by parlancex ( 1322105 ) on Wednesday November 09, 2011 @10:46AM (#37999108)

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

        by Anonymous Coward on Wednesday November 09, 2011 @10:54AM (#37999196)

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

        • 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:3, Funny)

        by BigMike ( 122378 )

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

      • Re: (Score:3)

        by tixxit ( 1107127 )

        Packing spheres

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

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

          • Re: (Score:2)

            by tixxit ( 1107127 )
            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.

      • Re: (Score:3)

        by Flavio ( 12072 )

        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)

          by UnknowingFool ( 672806 ) on Wednesday November 09, 2011 @11:33AM (#37999704)
          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.

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

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

        • 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)

        by Anonymous Coward

        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

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

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

      • Re: (Score:1)

        by Anonymous Coward

        Mercy me the Slashdot audience is getting dumber.

        Says user 1322105 to user 869860.

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

    by GameboyRMH ( 1153867 ) <`gameboyrmh' `at' `gmail.com'> on Wednesday November 09, 2011 @10:40AM (#37999040) Journal

    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)

      by Anonymous Coward

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

    • Add in shaking, and you're essentially describing simulated annealing [wikipedia.org].
      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.
  • 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.

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

      by fuzzyfuzzyfungus ( 1223518 ) on Wednesday November 09, 2011 @10:44AM (#37999086) Journal
      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...

      • Re: (Score:1)

        by Anonymous Coward

        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)

        by friedmud ( 512466 ) on Wednesday November 09, 2011 @12:35PM (#38000512)

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

    • 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

      • 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?

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

      • 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)

    by Anonymous Coward on Wednesday November 09, 2011 @10:45AM (#37999102)

    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)

      by pnewhook ( 788591 )

      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

      • 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

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

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

    • good thing my cylindrical display is only 2.5 times as large as its spherical pixels
    • 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!

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

  • the 2.7013 is an approximation of 1+1/sin(/5)

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

      by Chrisq ( 894406 ) on Wednesday November 09, 2011 @10:52AM (#37999178)
      Sod the slashdor character filter .. thats 1+1/sin(Pi/5)

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

        Some of us prefer Lisp notation, ya know.

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

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

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

      • Re: (Score:3)

        by hey! ( 33014 )

        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)

          by pnewhook ( 788591 ) on Wednesday November 09, 2011 @01:29PM (#38001272)

          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.

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

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

    • Re: (Score:3)

      by Chrisq ( 894406 )

      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)

    by JoshuaZ ( 1134087 ) on Wednesday November 09, 2011 @10:55AM (#37999212) Homepage

    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)

      by martas ( 1439879 )
      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 estimato
      • 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 techni

      • Re: (Score:2)

        by khallow ( 566160 )
        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 rela

        • Re: (Score:2)

          by martas ( 1439879 )
          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?

          • Re: (Score:2)

            by khallow ( 566160 )
            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.

    • Re: (Score:2)

      by Rumagent ( 86695 )

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

    • 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?

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

  • 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

    • 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 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

  • this research was funded by a grant from Hanes.

  • Considering a spherical horse in simple harmonic motion...

  • "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)

      by bityz ( 2011656 )
      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.

      • Re: (Score:1)

        by bityz ( 2011656 )
        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 :) )

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

  • 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]

  • So does this mean that we're one step closer to solving P = NP?
    • 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
  • Real-world application: Will this help me in the guess the number of gum balls in the container contests?
  • I was just able to get FIVE tennis balls into a container that usually holds three after applying this algorithm.
  • D(c)/D(s) = 2.7014. I'll stick to the old fashioned way, then...

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

Slashdot Top Deals

I have hardly ever known a mathematician who was capable of reasoning. -- Plato

Close