I asked a similar question on SciComp, but it is a little out of the domain, so I thought I'd give it a try here as well.

Give n points, I would like to place them in a periodic box (periodic such that the distance between two points "wraps around" to the other side) so that the minimum distance between any two points is as large as it can possibly be.

How do I do this? I imagine analytically this could be quite difficult, but is there at least a numerical procedure?

  • $\begingroup$ Place them on a hexagonal grid? I believe that is the densest packing. If the numbers don't fill up the points on the grid, it gets hairy. There are packing problems (some proposed by Kepler, and still unsolved) for spheres, perhaps 2D is simpler. $\endgroup$ – vonbrand Mar 24 '13 at 15:11
  • $\begingroup$ Yeah, it won't fill up the grid evenly. I'm trying to place 361 points at the moment. $\endgroup$ – Nick Mar 24 '13 at 15:15

This kind of problem is very hard. You might have a look at packomania which has solutions for many numbers of circles in squares and rectangles. Most of them are found experimentally and not proven to be maximal. You can almost incorporate the wraparound by shrinking the square or rectangle by the radius in each direction, but I don't think it gets the corners right.


I came up with the following, relatively easy to implement algorithm based on forces/constraints. I'm not sure if it always converges though.

Consider a box with width $w$ and height $h$ filled with $n$ particles represented as 2D vectors $p_i=(p_{i,x},\ p_{i,y})$

Now for each step, calculate for each pair of points ($p_i,\ p_j$) calculate the distance vector $r = p_j-p_i$ and use that to separate the points. First calculate a scaled version $r_s=\frac{F}{|r|^D}r$. F is a parameter that represents the amount of force and D represents how much force decreases with distance. For $D=1$, the force is constant (you get a unit vector) and for $D=3$ force decreases with the distances squared. Generally, a higher D yields better results. The force needs to be adjusted manually to the problem. Then move the points away from eachother by $r_s$: $$p_i(new)=p_i(old)-r_s$$ $$p_j(new)=p_j(old)+r_s$$

So now we have an algorithm to create the maximum distance between points, but the problem lies in the distance function. To find the shortest distance in a periodic box, imagine all the adjacent boxes point $p_j$ could be in. In 2D this wouldbe 9 boxes total and in 3D 27. The offset vector $v$ could take any of the following values. $$v=\left\{\begin{array}{c}v_x=-w,0,w\\v_y=-h,0,h\end{array}\right.$$ Now calculate all 9 possible distances $r_k=(p_j+v_k)-p_i$ and pick the $r_k$ with the smallest $|r_k|$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.