×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Faster Algorithm for Sphere Packing Discovered

Unknown Lamer posted more than 2 years ago | from the one-thousand-clown-bearings dept.

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

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

134 comments

Innovation! (5, Funny)

Anonymous Coward | more than 2 years ago | (#37998996)

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

Re:Innovation! (0)

Anonymous Coward | more than 2 years ago | (#38001020)

Dick Chainey allready solved this, He gets the guy next to him to store them.

Re:Innovation! (0)

Anonymous Coward | more than 2 years ago | (#38001156)

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.
I know there's a joke about putting balls into tight holes somewhere

Had to be asked. (4, Funny)

sgt scrub (869860) | more than 2 years ago | (#37999032)

Do you really need math to properly pack balls?

Re:Had to be asked. (4, Informative)

parlancex (1322105) | more than 2 years ago | (#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. (0)

Anonymous Coward | more than 2 years ago | (#37999128)

"pack balls" huh huhhuhuh uuhhu
Get over yourself. It's juvenile humor.

Re:Had to be asked. (5, Interesting)

Anonymous Coward | more than 2 years ago | (#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.

Re:Had to be asked. (1)

camperdave (969942) | more than 2 years ago | (#38000608)

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:Had to be asked. (0)

Anonymous Coward | more than 2 years ago | (#37999210)

Mercy me the Slashdot audience is getting dumber. Not only do they respond to an obvious joke not realizing it is humor, at least two idiots mod it up.

Re:Had to be asked. (3, Funny)

BigMike (122378) | more than 2 years ago | (#37999228)

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

Re:Had to be asked. (1)

tompaulco (629533) | more than 2 years ago | (#38000924)

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:Had to be asked. (0)

Anonymous Coward | more than 2 years ago | (#38002204)

Isn't is a spherical cow of uniform density in a vacuum

Re:Had to be asked. (2)

tixxit (1107127) | more than 2 years ago | (#37999270)

Packing spheres

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

Re:Had to be asked. (1)

robthebloke (1308483) | more than 2 years ago | (#38001832)

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:Had to be asked. (2)

Flavio (12072) | more than 2 years ago | (#37999292)

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. (0)

Anonymous Coward | more than 2 years ago | (#37999380)

No, it isn't a legitimate question. Packing balls has a sexual connotation.

Re:Had to be asked. (4, Informative)

UnknowingFool (672806) | more than 2 years ago | (#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.

Re:Had to be asked. (0)

Anonymous Coward | more than 2 years ago | (#38001124)

Would increasing the density of the spheres in a given volume however reduce the volumetric flow through the volume? What if the increased density of the catalysts speed up an endothermic or exothermic process, and the heat flow out of (or in to) the volume is already near its limits (as in, if the process needs heat, it's difficult to increase the heat flow into the middle of the system because the edge close to the external heat source is already near its point of ignition, vaporizing, freezing, etc)? Then increasing the sphere density might make the heat flow worse, no?

But then it still reduces to an engineering and design issue...

Re:Had to be asked. (1)

UnknowingFool (672806) | more than 2 years ago | (#38001342)

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.

Re:Had to be asked. (1)

marcosdumay (620877) | more than 2 years ago | (#37999820)

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:Had to be asked. (3, Informative)

Anonymous Coward | more than 2 years ago | (#37999514)

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. (2)

pnewhook (788591) | more than 2 years ago | (#38001114)

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.

Re:Had to be asked. (1)

mfnickster (182520) | more than 2 years ago | (#38001894)

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:Had to be asked. (1)

Anonymous Coward | more than 2 years ago | (#38002122)

Mercy me the Slashdot audience is getting dumber.

Says user 1322105 to user 869860.

Re:Had to be asked. (0)

Anonymous Coward | more than 2 years ago | (#38002758)

Have you noticed how close 2.7013 is to e (2.7182818284...)?
Maybe there's an efficient approximation to this algorithm.

Re:Had to be asked. (0)

Anonymous Coward | more than 2 years ago | (#37999622)

Do you really need math to properly pack balls?

Yes. We also need you to spit them out first.

Re:Had to be asked. (0)

Anonymous Coward | more than 2 years ago | (#38001176)

Once again, there is a world of difference between "sort these things" and "sort these things in the most efficient way possible."

There is a world of difference between "put these balls / spheres into a volume of x size" and "what is the smallest volume that x number of spheres of varying radius y0 through yX can take up?"

Just think about it for a few minutes. Do you need math to pack a suitcase? No. Do you need math to find the ABSOLUTE most efficient way in existence to pack your suitcase? Yes. Very yes.

Re:Had to be asked. (1)

alva_edison (630431) | more than 2 years ago | (#38001550)

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.

Interesting (2)

GameboyRMH (1153867) | more than 2 years ago | (#37999040)

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:Interesting (1)

Anonymous Coward | more than 2 years ago | (#37999218)

... 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 (0)

Anonymous Coward | more than 2 years ago | (#37999452)

or just use a sphere packer [spolargold.com]

Re:Interesting (1)

SomePgmr (2021234) | more than 2 years ago | (#38000000)

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.

2.7013 times larger at most? (1)

Bicx (1042846) | more than 2 years ago | (#37999050)

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? (3, Insightful)

fuzzyfuzzyfungus (1223518) | more than 2 years ago | (#37999086)

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:2.7013 times larger at most? (0)

Anonymous Coward | more than 2 years ago | (#37999158)

I thought fuel rods were typically bundles of thinner (and shorter) rods and/or flat disks?
(Pellet bed reactors depend on the fuel pellets moving through the core, so they can't really use any fancy packing.)

Re:2.7013 times larger at most? (0)

Anonymous Coward | more than 2 years ago | (#37999242)

Correct, most pellets per ft^2 is not the only thing fuel rod assemblies are designed for. You would also need plenty of room for moderator flow and as much contact as possible between the fuel pellets and the tubes they are in for a lower fuel center-line (temperature of the center of the pellet vs temperature of the surrounding moderator). Also, more importantly the pellets are cylinders rather than spheres.

Re:2.7013 times larger at most? (1)

Anonymous Coward | more than 2 years ago | (#38000314)

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? (3, Informative)

friedmud (512466) | more than 2 years ago | (#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....

Re:2.7013 times larger at most? (0)

Anonymous Coward | more than 2 years ago | (#37999092)

The cylinders can be considered to be spheres in a space of one less dimension.

Re:2.7013 times larger at most? (2)

donscarletti (569232) | more than 2 years ago | (#37999782)

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.

Re:2.7013 times larger at most? (1)

grimJester (890090) | more than 2 years ago | (#38000118)

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:2.7013 times larger at most? (1)

grimJester (890090) | more than 2 years ago | (#38000172)

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.

The math is even simpler (4, Funny)

Anonymous Coward | more than 2 years ago | (#37999102)

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

Re:The math is even simpler (0)

Anonymous Coward | more than 2 years ago | (#38000920)

Must ... resist ... pedantry ...

Can't, sorry.

It has to be exactly the same width. "1.0000 times larger" implies 1.00004 times larger is OK, but the problem instantly gets rather complicated if the cylinder is even slightly wider than the sphere.

Re:The math is even simpler (1, Funny)

pnewhook (788591) | more than 2 years ago | (#38001348)

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.

Re:The math is even simpler (0)

Anonymous Coward | more than 2 years ago | (#38001688)

You can achieve higher density by pressurizing the container.

At most 2.7013 times larger (0)

Anonymous Coward | more than 2 years ago | (#37999110)

Important detail from the article: if the cylinder is 2.7013000001 times larger then the math actually opens a rift to the heart of the universe where Azathoth froths and bubbles to the sound of demonic pipes and such like. This rarely ends well.

2.7013 Times (1)

Aladrin (926209) | more than 2 years ago | (#37999112)

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

Re:2.7013 Times (0)

Anonymous Coward | more than 2 years ago | (#38002528)

Isn't it a voluminous difference?

Great, but... (1)

JustinFreid (1723716) | more than 2 years ago | (#37999114)

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

Re:Great, but... (1)

Hentes (2461350) | more than 2 years ago | (#37999726)

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

For those of you wondering (1)

Chrisq (894406) | more than 2 years ago | (#37999168)

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

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

Chrisq (894406) | more than 2 years ago | (#37999178)

Sod the slashdor character filter .. thats 1+1/sin(Pi/5)

Re:For those of you wondering (2)

hey! (33014) | more than 2 years ago | (#38000406)

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

Re:For those of you wondering (4, Funny)

pnewhook (788591) | more than 2 years ago | (#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.

Re:For those of you wondering (0)

Anonymous Coward | more than 2 years ago | (#38001968)

So far as I know sqrt(3) and sqrt(7) don't have this gatecrashing habit.

sqrt(3) shows up a couple of times when you're talking about equilateral triangles [wikipedia.org].

Re:For those of you wondering (1)

Lexx Greatrex (1160847) | more than 2 years ago | (#38002400)

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.

Even better (0)

Anonymous Coward | more than 2 years ago | (#37999176)

I have developed an even faster algorithm although the one caveat is that the diameter of the cylinder can be at most 1.000 times larger than the diameter of the spheres being packed.

More Applications (1)

Thelasko (1196535) | more than 2 years ago | (#37999200)

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:More Applications (2)

Chrisq (894406) | more than 2 years ago | (#37999294)

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 (5, Informative)

JoshuaZ (1134087) | more than 2 years ago | (#37999212)

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:Major reasons we care about sphere packing (2)

martas (1439879) | more than 2 years ago | (#38000084)

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?

Re:Major reasons we care about sphere packing (1)

JoshuaZ (1134087) | more than 2 years ago | (#38000558)

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.

Re:Major reasons we care about sphere packing (1)

khallow (566160) | more than 2 years ago | (#38000970)

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.

Re:Major reasons we care about sphere packing (1)

martas (1439879) | more than 2 years ago | (#38001192)

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:Major reasons we care about sphere packing (1)

khallow (566160) | more than 2 years ago | (#38001748)

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:Major reasons we care about sphere packing (0)

Anonymous Coward | more than 2 years ago | (#38000228)

Umm - that may all be well and good, but 2.7013x the diameter of the spheres being packed, is only about 6 spheres.

Re:Major reasons we care about sphere packing (1)

Rumagent (86695) | more than 2 years ago | (#38001828)

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

Re:Major reasons we care about sphere packing (0)

Anonymous Coward | more than 2 years ago | (#38001986)

You, sir, are why I visit slashdot. (captcha - "subset" ... how appropriate)

2.7013 is almost e (2.71828) (0)

Anonymous Coward | more than 2 years ago | (#37999486)

Title says it all.

Think Slashdot isn't news for nerds anymore? (1)

bzipitidoo (647217) | more than 2 years ago | (#37999532)

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.

Re:Think Slashdot isn't news for nerds anymore? (1)

CrimsonAvenger (580665) | more than 2 years ago | (#38000236)

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.

Re:Think Slashdot isn't news for nerds anymore? (1)

friedmud (512466) | more than 2 years ago | (#38000372)

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

This should be useful in physics (1)

jmv (93421) | more than 2 years ago | (#37999938)

Considering a spherical horse in simple harmonic motion...

Needs Moar Topology (0)

Anonymous Coward | more than 2 years ago | (#38000108)

Spheres are topologically equivalent to a point. This problem is Topologically trivial :P

I was excited until... (1)

friedmud (512466) | more than 2 years ago | (#38000190)

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

Relation to Pi? (0)

Anonymous Coward | more than 2 years ago | (#38000638)

The author writes, "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."
I wonder if this has any connection with pi?
Two-thirds of pi = 2.09230071
          Coincidence????

the only caveat being it works for a spherical... (1)

mapkinase (958129) | more than 2 years ago | (#38000888)

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.

One step closer to P = NP? (1)

L473ncy (987793) | more than 2 years ago | (#38001150)

So does this mean that we're one step closer to solving P = NP?

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

JoshuaZ (1134087) | more than 2 years ago | (#38001556)

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 [doi.org] ) 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.

Too late (1)

craigminah (1885846) | more than 2 years ago | (#38001276)

A few years ago I worked in a job that put us on a boat in the ocean. My coworkers were golfers and a few were good at math so I asked them if they could calculate how many golf balls would fit into a 55-gallon drum. Never got an answer... Any algorithm would be nice, probably more a calculation of free space between the spheres but I never put much thought into it.

Re:Too late (1)

JoshuaZ (1134087) | more than 2 years ago | (#38001628)

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 [wikipedia.org]. 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.

Re:Too late (1)

craigminah (1885846) | more than 2 years ago | (#38002852)

Nice...so ~4657 golf balls will fit in a 55-gallon drum. Now I have to figure out how many tennis balls will fit in my dog's mouth...muahahahaha...
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...