Algorithm putting point into square with maximal minimum distance

views:

233

answers:

+12 Q:

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.

+2 A:

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.

Paul R 2010-04-27 17:54:51

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.")

ShreevatsaR 2010-04-27 18:13:38

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

Xavier Ho 2010-04-27 18:17:18

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

Rex Kerr 2010-04-28 03:57:00

+8 A:

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.

zaf 2010-04-27 18:09:20

Really nice! Now, how to generate the coordinates.

Xavier Ho 2010-04-27 18:11:21

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

zaf 2010-04-27 18:17:30

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

Xavier Ho 2010-04-27 18:21:35

Updated answer.

zaf 2010-04-27 18:26:54

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

Ravi Vyas 2010-04-27 18:27:54

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

zaf 2010-04-27 18:33:08

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.

Xavier Ho 2010-04-27 18:34:47

@zafmax 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

Ravi Vyas 2010-04-27 18:56:46

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

Xavier Ho 2010-04-27 20:54:13

@Ravi OK! @ShreevatsaR thanks for the cleanup!

zaf 2010-04-28 07:42:47

+2 A:

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/

Xavier Ho 2010-04-27 18:20:38

+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.)

ShreevatsaR 2010-04-27 18:27:12

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

Xavier Ho 2010-04-27 18:32:45

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

ShreevatsaR 2010-04-27 18:53:06

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

Xavier Ho 2010-04-27 20:53:15

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.

Matthieu M. 2010-04-28 06:37:03

ansaurus

tags:

views:

answers:

Algorithm putting point into square with maximal minimum distance

related questions