# Maximizing distance between points

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?

• 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. – vonbrand Mar 24 '13 at 15:11
• Yeah, it won't fill up the grid evenly. I'm trying to place 361 points at the moment. – Nick Mar 24 '13 at 15:15

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|$.