2
$\begingroup$

Given $x$ the number of circles of radius $r$, what is a good approximate size of the radius of a bigger circle which they fit in?

To explain in actual problem terms. I want to move units in a video games which take up a certain amount of area around, I don't want those units overlapping so I want the points there told to move to to be spaced far enough apart to make sure they aren't. I know how to make sure each point is far enough apart but i'm picking points randomly in a circle and then checking to make sure they are far enough apart.

The problem is if a circle is too small in size there simply isn't enough valid movement points for all the units and you get an infinite loop endlessly trying to find an answer that doesn't exist. If the circle is too large you end up with units spaced out over vast areas way out of proportion.

I do not need a perfect minimum radius answer I just need to be certain the amount will fit while not being too large. To show that I did think about it my rough guess was.

the square root of (amount needed) * (radius of each circle * 2)

$\endgroup$
2
  • $\begingroup$ Does the circle of each unit differ in radius? $\endgroup$
    – SeekingAMathGeekGirlfriend
    Commented Aug 29, 2015 at 1:09
  • $\begingroup$ no it's fine to have a single uniform radius for the smaller circles. $\endgroup$
    – user53961
    Commented Aug 29, 2015 at 1:16

2 Answers 2

Reset to default
1
$\begingroup$

There is an obvious lower bound: the area of the big circle has to be greater than the total area of the small circles, hence $\pi R^2 \geq \pi x r^2 $ gives $R\geq r\sqrt{x}$. On the other hand, one may consider the least $\rho\in\mathbb{R}^+$ such that inside the disk $\|z\|\leq\rho$ there are at least $x$ Eisenstein integers (an hexagonal packing). Then $x$ circles with radius $\frac{1}{2}$ fit inside a big circle with radius $\rho+\frac{1}{2}$, hence $x$ circles with radius $r$ fit inside a big circle with radius $(2\rho+1)r$. On the other hand, by surrounding every Eisenstein integer with an hexagon having unit diameter, we know that: $$ \pi\left(\rho+\frac{1}{2}\right)^2 = \frac{3\sqrt{3}}{8}\,x+O(\rho) $$ hence we may fit for sure $x$ circles with radius $r$ inside a big circle with radius $R$ if: $$ R \geq C r\sqrt{x} $$ and $C$ is a constant suitably greater than $\sqrt{\frac{2\pi}{3\sqrt{3}}}=1.0996361\ldots$.

$\endgroup$
2
  • $\begingroup$ based on your R >= r sqrt(x) then my guess of R = r sqrt(x) * 2 basically provides a good estimate? I get that I could make it smaller the * 2 multiplier is to make sure the computer doesn't spend an excessive amount of time searching for that last final perfect point when really i'll happily take a slightly larger circle to search in return for finding the answer in a reasonable time. $\endgroup$
    – user53961
    Commented Aug 29, 2015 at 1:57
  • $\begingroup$ @user53961: the radius $R=\frac{11}{10}r\sqrt{x}$ is fine. In order to place your circles, enlarge (a "binary search" algorithm is better) a circle centered in the origin until it contains $x$ or more Eisenstein integers, and place your small circles accordingly. You just need to be able to count the number of Eisenstein integers inside a circle centered in the origin, that is not difficult. $\endgroup$
    – Jack D'Aurizio
    Commented Aug 29, 2015 at 3:50
1
$\begingroup$

Assuming $R \gt\gt r$

It has been proved by Joseph Louis Lagrange in 1773, that to pack circles of identical radius within an area, the highest density stacking is the hexagon arrangement. And the max density of hexagon stacking is $\frac{\pi}{\sqrt{12}}$. Here density means the portion of the area of the circle of radius $R$ is covered by the circle of radius $r$. Hence for circle R and r,

$x \cdot \pi r^2 \le \frac{\pi}{\sqrt{12}} \cdot \pi R^2$

$R \ge \sqrt{\frac{\sqrt{12}}{\pi}} \sqrt{x} r = 1.050075 \sqrt{x} \cdot r$

See Circle packing - Wikipedia.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .