Search code examples
algorithmgeometrypacking

Algorithm putting point into square with maximal minimum distance


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:

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.


Solution

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

    alt text

    Pages 109 and 110 contain a list of references.