Placing small circles randomly inside a larger circle, where no two small circles intersect

Question

Sorry if this is the wrong place to ask, was unsure...let me know if it belongs some where else.

So i am trying to work out a way to write an algorithm to place a series of small circles of a set radius (all the small circles have the same radius), inside a larger circle.

The small circles cannot overlap each other or overlap the main circle's perimeter, and they are placed randomly inside the main circle.

I am wanting it to then populate as many circles as it can until it is not possible to place any more circles without overlapping another.

This obviously means that each run through depending on the random placements will potentially give different amounts of maximum number of circles inside the big circle - thats fine, and thats some what the point.

Does any one have any advice how i might approach the logic for this?

Answer 1

Suppose the small circles have radius $r$, and the large circle has radius $R$. If there are less than, say, 100 small circles, then the following simple algorithm should be fast enough:

1. Generate a larger number, say 1000, of points at random locations inside a circle of radius $R-r$ (this smaller radius guarantees that a small circle centered at each point will fit within the radius-$R$ circle).
2. Calculate all roughly 500000 pairwise distances between points.
3. Sort these distances in increasing order.
4. Loop through the distances. For each distance $< 2r$, randomly pick either point and delete it. (Such a distance implies that there could not be a radius-$r$ circle at both points without overlap.) If the distance refers to a point that has already been deleted, ignore it.
5. All points that remain are at least $2r$ apart from each other, so you can put a radius-$r$ circle at each.

If this is too slow, you could use a grid to speed things up: Make the step size of the grid $2r$, and only bother comparing point pairs that are in the same grid cell or adjacent grid cells. (Every pair of points $x \in X, y \in Y$ for 2 non-adjacent grid cells $X$ and $Y$ is at least $2r$ apart, so we don't need to bother testing them.)

NOTE: This could leave holes where a small circle could fit. My intuition is that having enough initial potential centre points will make this unlikely. You could use a smaller grid, of step size $r$, to find some (not necessarily all) of these holes: A grid cell that does not overlap any circle is definitely a "hole" (a circle can be added there).

In case you're wondering, the problem you "really" want to solve is to find an independent set of vertices in a graph in which you have a vertex for each circle and an edge between 2 points whenever they are at distance $< 2r$. The general form of this problem is NP-hard, though I suspect there is enough additional structure here that a faster solution (maybe poly-time, maybe not) is possible.