Point packing problem

1. Apr 25, 2014

EvoG

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.

2. Apr 25, 2014

mathman

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

3. Apr 25, 2014

Staff: Mentor

Except for at the corners and edges of the enclosing "box".

4. Apr 25, 2014

HallsofIvy

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. Apr 26, 2014

mathman

I don't think so. Using cubes will fill up the box neatly. Spheres will pack more tightly.