Serving the Quantitative Finance Community

 
User avatar
Chukchi
Topic Author
Posts: 0
Joined: December 15th, 2001, 3:43 am

Packing

July 10th, 2005, 1:16 am

How many n-dimensional hyperspheres with diameter equal to 1 could be packed into n-dimensional hypercube with side 2?
 
User avatar
exotiq
Posts: 2
Joined: October 13th, 2003, 3:45 pm

Packing

July 10th, 2005, 3:40 pm

I'll take a shot at saying the naive answer is 2^nFor n=1, the answer is trivially two if we understand the "spheres" to be 1-intervals in a 2-interval "cube". n=2 is the case of four circles in a square, and n=3 is the case of 8 balls in a cube, etc. It would be easy to show by induction that adding a dimension preserves the projection from n -> n-1, and the "height" of the spheres is half as high as a cube, so their number may be doubled.What I may be missing is the geometry of being able to fit more spheres between the 2^n at higher dimensions, because for n>1, there is space wasted...
 
User avatar
bertstein
Posts: 0
Joined: December 22nd, 2003, 4:54 pm

Packing

July 11th, 2005, 7:16 am

In fact, when n = 4, there is enough space to fit one extra ball in the middle - so 17 hyperspheres when n = 4.Is this easier or harder than the hexagonal packing problem?
 
User avatar
Chukchi
Topic Author
Posts: 0
Joined: December 15th, 2001, 3:43 am

Packing

August 29th, 2005, 1:11 pm

I expect to see some kind of Generalized Catalan Numbers as an answer to this problem.