1

I am wondering how can I solve following problem.

Arrange randomly n points inside a square of the side length a under the condition that the distance between any two points may not be smaller than 1.

I would like to see how can it be solved.

Beginner in fort
  • 37
  • I think this needs clarification. Are you looking for an algorithm that will always produce such a random selection? Are you looking for a bound on n such that such a configuration is possible? What have you tried? – lulu Jul 11 '15 at 15:47
  • I was trying to make nrandom numbers in the selected a side lenght but I do not know how to make sure that the point-to-point distance between every of the n points will be always bigger than 1. – Beginner in fort Jul 11 '15 at 15:50
  • Telling us the reason why you want to do this will probably be helpful. –  Jul 11 '15 at 15:55
  • It is the introduction exercise to the crystallography – Beginner in fort Jul 11 '15 at 15:58
  • 1
    Then use the "image erasing" solution, or do it by hand with a carton disk. –  Jul 11 '15 at 16:01
  • I would surely do that if I did not have to do it in fortran :) I am asking here, because I was thinking that there is some universal formula for such a problem. – Beginner in fort Jul 11 '15 at 16:05
  • 1
    Then use the "brute force" solution, checking all distances before you insert a new random point. –  Jul 11 '15 at 16:41

1 Answers1

2

If the points really need to be random, then draw random points and place them in the square if there is not already other points at distance less than 1.

Anyway, at some moment the procedure can start looping forever if there is no room left, but this is difficult to establish.

An approximate solution can be implemented by means of a high resolution image of the square. Every time you place a point, erase the disk around it, and then avoid placing points in an erased area.

You can think of an exact solution, by means of a solution to the "Dynamic Planar Nearest Neighbors" problem, but this can be quite arduous.

  • One interesting difficulty: if you really need to put in n points (up to the maximal n) then you can't put the first point in randomly. I don't know what the OP had in mind there. – lulu Jul 11 '15 at 16:10