Square intersection solver

Question

I'm looking for an efficient way to move hundreds of uniform, possibly intersecting squares away from each other, so they no longer intersect. The resulting new positions should be as close as possible to the original coordinates.

Is there such an algorithm?

Answer 1

Introduce the shift variables Xi+, Xi-, Yi-, Yi- and solve the linear problem that minimizes the sum of the variables under constraints that express the non-overlap like (Ui + Xi+) - (Uj - Xj-) >= S, (Vi + Yi+) - (Vj - Yj-) >= S or similar.

If you are not familiar with linear programming, you should read about: http://en.wikipedia.org/wiki/Linear_programming