Algorithm putting point into square with maximal minimum distance

Question

I'm stuck on this: Have a square. Put n points into this square so the minimal distance (not necessary the average distance) is the highest possible.

I'm looking for an algorithm which would be able to generate the coordinates of all points given the count of them.

Example results for n=4;5;6:

Please don't mention computing-power based stuff such as trying a lot of combination and then nitpicking the right one and similar ideas.

Answer 1

This is the circles in square packing problem.

It is discussed as problem D1 in Unsolved problems in geometry, by Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy, page 108.

Pages 109 and 110 contain a list of references.

Answer 2

You could do an N body simulation where the points repel each other, perhaps with a 1/r^2 force. The movement of the points would obviously be constrained by the square. Start with all the points approximately in the centre of the square.

Answer 3

Mikulas, I found a page full of image examples of possibly optiimal, or currently best known solutions. It's not mine, so use it with your own risk.

See

http://www.ime.usp.br/~egbirgin/packing/packing_by_nlp/numerical.php?table=csq-mina&title=Packing%20of%20unitary-radius%20circles%20in%20a%20square

Source:

http://www.ime.usp.br/~egbirgin/packing/packing_by_nlp/