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

1 Answer 1

This is a convex optimization problem:

$$\min R$$

subject to

$$\begin{aligned} f(x, \pi) &= 1 & &\forall x \in X, \pi \in P \\ d(x,y) &\geq R & & \forall x,y \in X \\ d(x,\pi) &\geq R & & \forall x \in X, \pi \in P \end{aligned}$$

where:

  • $X$ is the set of $N$ points
  • $P$ is the set of faces of the cuboid
  • $f(x,\pi)$ is an indicator function indicating that $x$ is on the right side of $\pi$

Since the objective is linear and the constraints are quadratic, this can be solved by semidefinite programming.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.