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
    Gold Member

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


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

Similar Discussions: Point packing problem
  1. Close packing (Replies: 5)

  2. Sphere packing problem (Replies: 7)

  3. Packing Problem (Replies: 11)