I've stumbled upon this sphere packing question, and now I have another related one.

How can I have a function that returns a sphere packing with a target volume fraction? Sphere can obviously have different radii.

Thanks for your hints!

  • $\begingroup$ I suspect this is a special case of the NP-complete knapsack problem and hence no polynomial algorithm exists. $\endgroup$ Sep 20, 2017 at 17:49
  • $\begingroup$ Yes, it is, but I am also content with some brute-force approximated solutions. $\endgroup$
    – senseiwa
    Sep 21, 2017 at 9:52
  • $\begingroup$ This sounds like it could be an interesting puzzle, but I think I might be missing the point. Can you be a bit more specific? What are the constraints on the (radius distribution of/number of/placement of/etc.) spheres? Why not just stop the linked function when the right volume is reached? Why would returning a single sphere of the target volume be wrong (aside from being boring)? $\endgroup$ Oct 3, 2017 at 2:32
  • $\begingroup$ The most probable constraint is passing a probability distribution to the computation, so that radii will adhere (more or less) to it. Yes, I'd like to stop when the target volume ratio is obtained, but a single sphere would be so boring, I agree with you! $\endgroup$
    – senseiwa
    Oct 5, 2017 at 14:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.