Point packing problem

  1. 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. jcsd
  3. mathman

    mathman 6,381
    Science Advisor
    Gold Member

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

    Staff: Mentor

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

    HallsofIvy 40,212
    Staff Emeritus
    Science Advisor

    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.
  6. mathman

    mathman 6,381
    Science Advisor
    Gold Member

    I don't think so. Using cubes will fill up the box neatly. Spheres will pack more tightly.
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook