Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a (3D) cuboid and an integer N, how can I position N spheres that fit inside without touching such that the radius of the spheres is maximised?

Is there some group theory that I need to know, or are there "jiggling" algorithms that can calculate an answer?

Actually, only the centres of the spheres need to be inside. If I was concerned with a cube I think I could get away with scaling the solution after it was found, however I'm not sure if that's possible.

Put another way, I would like to find the N points inside a given cuboid that maximises the minimum distance between any two.

What algorithm does this use? Can this be adapted? http://www.randomwalk.de/sphere/incube/spheresincube.html

This link to wikipedia is infuriating... http://en.wikipedia.org/wiki/Packing_problem#Spheres_in_a_cuboid

If an algorithm or general method that finds the optimal solution is not known or does not exist, is there one that will find a approximate or "good enough" solution?

share|improve this question
    
You may find something useful at hydra.nat.uni-magdeburg.de/packing/scu/scu.html –  Gerry Myerson Sep 13 '12 at 12:14
    
Also of possible interest, ics.uci.edu/~eppstein/junkyard/spherepack.html –  Gerry Myerson Sep 13 '12 at 12:17
    
My apologies, I have corrected the first paragraph. I've seen your first link, and basically wish to 1. Replicate the calculations they made, 2. Generalise to spheres in a cuboid, 3. Correct to allow the spheres outside iff their centres remain inside. The 2nd link looks useful, I will check it for information on the algorithms/methods used. Edit: From your 1st link: combinatorics.org/Volume_11/PDF/v11i1r33.pdf Mentions the "Billiard algorithm" and how it was adapted. This may be what I am after, I will give it a read. –  Dijkstra Sep 13 '12 at 14:05
2  
Allowing part of the sphere outside the cuboid doesn't change the problem: increase the dimensions $2r$ in each dimension and demand the entire sphere is inside is the same. –  Ross Millikan Sep 13 '12 at 14:17
    
My question is the same, but for spheres. In other words, I would like to find the N points inside a given sphere that maximises the minimum distance between any two. How can I position N equal spheres inside a larger sphere, as they stay as distant as possible? Could anybody give me a hint or a reference please? –  tSirmen Sep 20 '12 at 11:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.