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.

Diuretic

Is this the same as "Circles in square"? en.wikipedia.org/wiki/Packing_problem#Circles_in_square – Covell

Let the OP declare if it's homework or not, please. – Stilton

@Covell i dont think this would be related to the circles in squares, there the circles touch , here the points repel , even if you assume the points to be centers of the circle the circles would overlap. :) – Kila

@Ravi look at the image when n=7, are all the circles touching? no. – Covell

@zaf: I've just checked the first few solutions for 3;6;7, but I thing it it's the same (or at least do the job very well). Can you please post it as an answer so I can mark it? Thanks. | @ravi: It's obviously not homework since it's not so obvious to solve. I've just been wondering about it ever since I saw all the solutions - and I wanted a proof they are actually not wrong. – Diuretic

From the wiki entry: "Pack n unit circles into the smallest possible square. This is closely related to spreading points in a unit square with the objective of finding the greatest minimal separation, dn, between points[1]. To convert between these two formulations of the problem, the square side for unit circles will be L=2+2/dn" So yes, the two problems are equivalent. – Arlana

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.

Covell

Really nice! Now, how to generate the coordinates. – Stilton

You guys want the next page with the list of references? – Covell

@zaf, could you give us the title and author of that book, if it has more information on this topic? (Or possibly other puzzles?) – Stilton

I do agree the distances would be the same but this would not be the solution for the question. Here the points can lie on the edge of the square but in the circles in a square the centers cant not be on the edge unless r="0". – Kila

@Ravi The authors write "these two problems are equivalent". You must disagree with them otherwise you wouldn't have down voted my answer. – Covell

Equilvalent problems, different sets of solutions. Either way, the maximal minimum distance of these points would be the radius of the sphere. It's just a matter of fitting another smaller square to get a quick approximation of what you need with points. – Stilton

@Covell max diameter of 4 circles that can be packed in a unit square = 0.5 max distance between 4 points in a unit square = 1 , also when n is 4 the points are the vertices but the centers of the circles are not. Also the author starts the paragraph stating the square is of unit length and finishes it with a square of d+1 length. The answer you provided does in deed provide a solution to the distance between them , but does not state how do we do it. ps : I did not vote your answer down :D – Kila

Ah right. Corrected, the distance is the diameter of the circle, not the radius! Thanks Ravi. – Stilton

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.

Menace

Yes, you "could". But would it be any good? (What guarantees can you give? Can you say it is within a certain factor of optimal, say?) (See OP's comment in question: "Please don't mention computing-power based stuff such as trying a lot of combination and then nitpicking the right one and similar ideas.") – Feldt

I can see an N body simulation being helpful for quick approximations, though. – Stilton

"Maximum minimal distance" is equivalent to a 1/r^infinity potential. If one wanted to create approximations this way--which strikes me as a good heuristic method--one should start with 1/r^2 but then move to higher powers when one was close to a solution. – Dregs

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/

Stilton

+1. I suspect these are actually optimal (numerically), for two reasons: they use the word "solve" in describing their algorithms, and different n have different number of trials, suggesting that possibly they reached optimality early. (To be sure, it would be better to look at the source and see whether they stop only when duality gap goes to 0, or what.) – Feldt

@ShreevatsaR: Optimalism is another topic to prove. ;] Good enough is good enough, sometimes. – Stilton

Yes, I know, I'm just saying that not only are these good enough, they do seem to be actually optimal as well. – Feldt

Some of the higher n ones don't look convincing, though. (50+) – Stilton

Interestingly, I haven't seen a solution where there was not at least 2 points in 2 consecutive corners of the square. Of course, you still have n-2 points to place. – Numbskull