Register to reply 
Point packing problem 
Share this thread: 
#1
Apr2514, 01:11 PM

P: 1

I have a problem and I'm not sure if it has been formulated and/or solved before.
Suppose you have a finite ndimensional space in which each dimension is constrained to [0,1]. I need the maximum number of points p that can be put in this space such that no two points are closer than some threshold t. For instance, if n = 2 and t = 1, then p = 4. Think of the corners of a square with sides of length 1. If n = 2 and t = 1.4, then p = 2, since opposite corners of a square with sides of length 1 are > 1.4 distance apart. In general, my n is going to be large (>10000) and my t will certainly be greater than 1. I don't need a perfect formula. An approximation that gets me to within a factor of about 2 of the actual solution would be good enough. I suspect this problem may be reducible to the sphere packing problem which has only been solved for up to 8 dimensions, but I thought I'd check with the experts to see. 


#2
Apr2514, 02:44 PM

Sci Advisor
P: 6,112

It does look like a sphere packing problem with radius = t/2.



#3
Apr2514, 03:10 PM

Mentor
P: 21,409




#4
Apr2514, 05:19 PM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,691

Point packing problem
But since the "t" is minimum possible distance, the corners not really relevant. Using spheres of radius t/2 should give the same result as using cubes with side length t.



#5
Apr2614, 03:17 PM

Sci Advisor
P: 6,112




Register to reply 
Related Discussions  
Geometry Problem involving packing Hexagons into Circles  Differential Geometry  1  
Operational research : Shelf packing problem  Calculus & Beyond Homework  4  
Packing Problem  General Math  11  
Sphere packing problem  General Math  7  
Volume problem  Closest packing  Introductory Physics Homework  4 