# Algorithm to randomly place circles at least $D$ distance away from one another

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?

-
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 cs.virginia.edu/~gfx/pubs/antimony 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

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