0
$\begingroup$

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?

  • 0
    You may find something useful at http://hydra.nat.uni-magdeburg.de/packing/scu/scu.html2012-09-13
  • 0
    Also of possible interest, http://www.ics.uci.edu/~eppstein/junkyard/spherepack.html2012-09-13
  • 0
    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: http://www.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.2012-09-13
  • 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.2012-09-13
  • 0
    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?2012-09-20
  • 0
    @tSirmen Answers are intended for answers only. Please don't post related questions as answers. Either post a comment or another question.2012-09-20

0 Answers 0