Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to work out how to write an algorithm to randomly place circles of $R$ radius, in a $2D$ rectangle of arbitrary dimensions, such that each placed circle is at least $D$ distance away from other circles in the rectangle.

Can anyone help me how to deduce such an algorithm, or perhaps point to some research that may cover this?

Thanks in advance!

share|cite|improve this question
Not quite sure what you mean by distance here, but assuming you want the nearest points on the circumferences of your circles to be $D$ apart for each pair of circles, you need the centres to be at least $2R+D$ apart. – Mark Bennet Sep 11 '11 at 17:46
Yes that is exactly what I meant, thanks for the clarification – Paul Newman Sep 11 '11 at 17:49
In computer graphics, this is known as Poisson-disk sampling. Google will find you lots of references to efficient algorithms, though the easiest (and slow) way is to just keep placing disks randomly on the domain one by one, rejecting those that are too close to previously placed disks. (Of course, you need a termination criterion, but that's only hard if you want to guarantee that the arrangement is maximal...) – Rahul Sep 11 '11 at 18:07
Echoing @Rahul, see for instance. – lhf Sep 11 '11 at 19:43
You should specify if you simply want any random distribution, or if you want an algorithm that yields a pre-specified distribution on the set of all such configurations. – Greg Martin Nov 11 '11 at 2:27

This (if I understand it right: all permissible configurations are equiprobable) would be equivalent, in a statistical physics context, to generating samples from a Canonical ensemble of "hard disks" (2D version of the "hard spheres" system).

The standard procedure is Montecarlo simulation, via Metropolis algorithm: starting from a permisible configuration (you can find it by hard trying), you make small random displacements and either accept it (if the disks do not overlap), elsewhere keep ("repeat") the previous position. It is shown that, in the long run, the generated samples follow the desired distribution (though, of course, the succesive samples are not independent).

share|cite|improve this answer
Not strictly true, as the set of permissible configurations of $n$ disks may not be connected (as a subset of $\mathbb{R}^{2n}$). For instance, in a rectangle just over $2$ disks wide and just high enough to hold a third disk, you can't get from a right-side-up triangle to an upside-down triangle. But when the disks aren't frozen, this is definitely the way to go. – mjqxxxx Jun 20 '15 at 6:46

It's not clear precisely what you mean by "random" here, but one interpretation is that the congiguration (the list of centres of the $N$ circles) should be uniformly distributed in the set of allowed configurations (a subset of ${\mathbb R}^{2N}$, presumably of positive measure). One algorithm to do this would be to generate a random $N$-tuple of points in the rectangle, accept it if all the distances between the centres are at least $2R+D$, otherwise reject it and generate a new $N$-tuple, continuing until you accept an $N$-tuple.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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