Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sphere packing problem

  1. Jun 5, 2008 #1
    How many n-dimensional unit vectors from [itex]\mathbb{C}^n[/itex] can you pack in a set such that for any two vectors, [itex]\left<a, b\right>\leq\delta[/itex] for some delta between 0 and 1?
    (<a,b> denotes the inner product).

    This reduces to packing of n-2 dimensional spheres on a n-1 dimensional sphere, if that helps.

    EDIT: on second thought I'm not sure if this reduces to a sphere packing problem.
    Last edited: Jun 5, 2008
  2. jcsd
  3. Jun 6, 2008 #2
  4. Jun 6, 2008 #3
    Without specifying what the set is, it's hard to comment. Also, I've only ever seen sphere packing conisdered for real numbers; not sure how the extension to complex would play out...
  5. Jun 6, 2008 #4
    The max size of the set depends only on [itex]\delta[/itex], which determins how close two vectors from the set can be. [itex]\delta =0[/itex] then the max size is the dimension; [itex]\delta =1[/itex] then it's infinite.

    EDIT: I made a typo in my first post. The requirement is that

    [tex]\left|\left< a,b\right>\right| \leq\delta[/tex]. Note the modulus operator.
  6. Jun 10, 2008 #5
  7. Jun 11, 2008 #6
    Supposing we restrict it to R^3 and are interested in the limiting case where delta -> 1. Obviously this is not your full problem, but at least I can say something about it, whereas the full out problem seems pretty hard. What I say can be generalized to R^n as well.

    Suppose you are adding unit vectors one by one, trying to keep their tips spaced as far apart as possible on the unit sphere (or equivalently, trying to keep their angles as big as possible for a given number of vectors). For 2 vectors, you would place them at antipodes (opposite points on the sphere), 180 degrees. For 3 vectors, 120 degrees in the plane. 4 vectors, tetrahedron (~109 degrees). 5 vectors, a more complicated shape, 12 vectors, the points on a dodecahedron, etc etc.

    For small numbers of vectors, adding each additional vector causes massive changes in the configuration of all previous vectors, and the angle jumps drastically (180 -> 120 -> 109 ..). However, when there are already a ton of vectors on there, say, 100, then the ball looks like a prickly sea urchin, and if you add one more vector, then the other vectors on there can accommodate it by all shifting very slightly. Everything from now on is assuming a large number of vectors.

    Thus for large numbers of vectors, the the surface area of the unit sphere is uniformly sprinkled by the different vector tips. Further, if the vector tips are used to triangulate the surface of the sphere (Delaunay triangulization would work nicely), then as the number of vectors becomes large the triangles will become approximately equilateral.

    You can use the Euler characteristic to find that the number of triangular faces is f=2(v-2) where v is the number of vectors. (v-e+f=2, and e=3f/2 since each face has 3 edges, which would double count each edge)

    Since the triangles take up roughly equal surface area on the sphere, f*A = 4*pi, or A = 4*pi/f where A is the area of a single triangle. Additionally, since the triangle is approximately equilateral, the area is related to the edge length by A = d^2*sqrt(3)/4, or d = sqrt(4A/sqrt(3)).The angle between 2 neighboring vectors is then θ ~= arcsin(d) ~= d for small angles.

    Putting this all together,
    in the limit as v-> infinity, θ = sqrt(4*(4*pi/2(v-2))/sqrt(3))

    You can invert this and find
    in the limit as θ -> 0, v = 8*pi/(sqrt(3)*θ^2) + 2

    assuming I didn't make any algebra mistakes in there...

    your delta, by the way, is cos(θ), as that is the way the inner product relates to angle.
    Last edited: Jun 11, 2008
  8. Jun 12, 2008 #7
    If I understood correctly, you gave an approximate answer in the limiting case using a greedy packing algorithm. That's interesting. Do you know whether the greedy algorithm in this case will produce an optimal unit vector packing?
  9. Jun 12, 2008 #8
    I think it is optimal. To be rigorous, you would have to prove that: given an optimal packing algorithm, the delaunay triangulization (or any other triangulization) of the configuration will produce triangles that approach equilateral triangles in the limit as θ -> 0.

    If there are multiple optimal packing algorithms aside from rotations of the original algorithm (I doubt it), then you only need to prove it for one algorithm.
    Last edited: Jun 12, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Sphere packing problem
  1. N-sphere math problem (Replies: 10)

  2. Packing Problem (Replies: 11)

  3. Point packing problem (Replies: 4)