1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Point packing problem

  1. Apr 25, 2014 #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. Apr 25, 2014 #2


    User Avatar
    Science Advisor

    It does look like a sphere packing problem with radius = t/2.
  4. Apr 25, 2014 #3


    Staff: Mentor

    Except for at the corners and edges of the enclosing "box".
  5. Apr 25, 2014 #4


    User Avatar
    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. Apr 26, 2014 #5


    User Avatar
    Science Advisor

    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 this thread via Reddit, Google+, Twitter, or Facebook