3
$\begingroup$

I am wondering how can I solve following problem.

Arrange randomly $n$ points inside a square of side $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.

$\endgroup$
  • $\begingroup$ Could you say more about which question you are trying to answer? Do you want an algorithm that randomly places the points for you, for fixed $a$ and $n$? $\endgroup$ – Patrick Sanan Sep 9 '15 at 13:11
5
$\begingroup$
  1. Choose n random points in the unit square.
  2. Compute the minimum point-to-point distance, $D$.
  3. Re-scale the space by $1/D$. The minimum point-to-point distance is now equal to 1.

Edit:
The best method to do step 2. depends on many things. If don't have too many points you can just compute (using matlab syntax):

dmin=1;
for i=1:n
  for j=i+1:n
    dmin = min( dmin,norm( p(i,:)-p(j,:) ) );
  end
end

This brute force method will take $\mathcal{O}(n^2)$ time. If you have many, many points it may be worth using an $\mathcal{O}(n\log(n))$ algorithm using a divide and conquer approach. See the wikipedia page for more information.

$\endgroup$
  • $\begingroup$ Yes, that is helping me a lot, but I have one more question. How can I solve the second point of your post? It is making me the biggest problem actually. $\endgroup$ – Beginner in fort Jul 11 '15 at 15:37
  • $\begingroup$ This is a bad idea. There's no limit to how close two points may by chance lie, and so the the scale factor could sometimes be wild. $\endgroup$ – DarenW Sep 8 '15 at 21:38
  • $\begingroup$ @DarenW The OP said "random" so perhaps that is a desired rather than a problem. Once you start excluding cases that are too "wild" things are no longer truly random. If the OP is willing to accept a non-random set of points that meets some other criteria then there are clearly other options. Your answer, for example, is a good suggestion if the OP wants relatively uniform coverage rather than randomness. $\endgroup$ – Doug Lipinski Sep 9 '15 at 0:38
3
$\begingroup$

If $n$ is too large and the side length of your squarer $a$ is fixed then there may not be a solution to your problem. If you are willing to increase the size of the square to fit the points then the solution by @DougLipinski will work.

If the square size if fixed (which is why I assume you asked the question in the first place), then the re-scale step in his solution may push points outside the square.

You can actually estimate an upper bound on the number of points that will fit inside your square by computing the number of points that make up a tessellation of the square.

$\endgroup$
2
$\begingroup$

The problem of finding the smallest $a$-square that can contain $n$ points whose distance is not less than $1$ is equivalent to the circle packing in a square problem, see e.g Equivalence between circle packing and point packing. Info about this problem can be found also in Circle Packing and a list of optimal or best known solution in The best known packings of equal circles in a square.

This is, as far as I know, a still unsolved problem: the answer to the OP question depends on how close is the desired solution to the optimal one, or on how big is $n$ for fixed $a$.

If we look for a far from optimal solution, the answer by Doug could be viable. On the contrary if we approach the optimal limit, the random scatter and rescale approach will give unfeasible solutions, as pointed out by dpmcmlxxvi in his answer.

The problem is not defined in such a way that a unique or best answer exists, but I would proceed in the following way in $n$ is large enough, but still not too close to the optimal/best known solution.

  1. arrange the $n$ points on an hexagonal lattice whose envelope is approximately square. (See OEIS A093766 for the properties of this lattice.)

  2. if the side of this square is less then $a$, rescale it to tightly fit inside the $a$ square.

  3. after rescaling apply a small perturbation, in order to give a "random" appearance to the solution.

If $n$ is close to the optimal/best know solution, than simply do a table lookup from a list of the known solutions.

$\endgroup$
1
$\begingroup$

Looks like you may want to use a Halton Sequence or a Sobol Sequence. These are sets of points distributed in a square, looking random, but avoiding any two being too close together.

The articles on wikipedia are a good start.

$\endgroup$
1
$\begingroup$

You can check Poisson-disc. It produces points that are tightly-packed, but no closer to each other than a specified minimum distance.

$\endgroup$
  • $\begingroup$ Welcome to SciComp.SE. Can you please explicitly provide your affiliation with the project you link to? Furthermore, can you please provide a description of the algorithm that is used in Poisson-disc (and possible references)? The link might be broken in the future, but the description can still be valid. $\endgroup$ – nicoguaro Sep 10 '15 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.