- #1
EvoG
- 1
- 0
I have a problem and I'm not sure if it has been formulated and/or solved before.
Suppose you have a finite n-dimensional 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.
Suppose you have a finite n-dimensional 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.