# Expected area covered by circles inside a square

$$n$$ circles of radius $$r$$ are to be placed randomly inside a square of side length $$l$$. What is the expected area the circles will enclose?

Edit: As @Mirko suggested, we define random placement of the circles by picking points from a square of side length $$l-2r$$ concentric to the initial one from a uniform distribution and using each one as a center for a specific circle.

The problem I'm facing is that I do not know how to statistically account for overlaps with the circles. I have tried to divide the square into little square "cells" of side $$2r$$ such that each circle can exist in one of the cells and obtained an expression for the probability of $$k$$ circles to exist with no overlap. However, this approach drastically understates the actual probability as it doesn't account for circles existing in between cells.
Any alternative approach would be greatly appreciated.

• This is a quite interesting problem (+1) Commented Jan 31, 2021 at 23:15

So we're assuming $$l\ge2r$$. Let's take the square in Cartesian coordinates to be $$S:=[-l/2,\,l/2]^2$$. The point $$(x,\,y)$$ therein falls within a circle centred at $$(u,\,v)\in S^\prime:=[-(l/2-r),\,l/2-r]$$ iff$$(x-u)^2+(y-v)^2\le r^2.$$Let $$f(x,\,y)$$ denote the probability of this when we take $$U,\,V$$ to be Uniform IIDs on their support; the same treatment of $$X,\,Y$$ makes the probability a random point lies in at least one of the circles$$1-\int_S(1-f)^ndxdy,$$so multiplying this by $$\pi l^2$$ gives the circles' union's mean area. Note the $$n\to\infty$$ limit is less than $$\pi l^2$$ because some points have $$f=0\implies\lim_{n\to\infty}(1-f)^n=1$$. In particular, a point in $$S$$ may be as far as $$r\sqrt{2}$$ from the nearest point in $$S^\prime$$.

So now we have two tasks: compute $$f$$, then compute $$\int_S(1-f)^ndxdy$$. Note $$f$$ is the proportion of the area of $$S^\prime$$ within a distance $$r$$ of $$(x,\,y)$$. While obtaining $$f$$ as a piecewise function is feasible, I suspect the integrals are numerical for large $$n$$.

• Thanks! Do you think there would be a way to obtain an approximate form of the result when $r << l$ for large $n$ without having to evaluate non-elementary integrals? Commented Jan 14, 2021 at 17:48
1. the geometrical approach

The problem is clearly scale invariant.
So let's take the square $$Q=[-1,1]^2$$, inside which lay $$n$$ "coins" of radius $$r \le 1$$, which may also overlap themselves.

The coins are randomly i.i.d. uniformly distributed, with centers $$X_k=(x_k,y_k)$$ onto the square $$R =[ -1+r,1-r]^2$$.
We want to determine the expected area $$A$$ of the space left uncovered in $$Q$$, which is the complement of the union of the $$n$$ coins. The area can vary from a maximum of $$4- \pi r^2$$ when the coins are totally piled, down to $$4-n \pi r^2$$ if the space allows to place the coins non-overlapping, and then ,at increasing of $$n$$ and/or $$r$$, down to the max packing, till arriving for large $$n$$ to a very minimum of $$(4-\pi) r^2$$, when the square is almost totally covered, except for the corners where the space with the tangent circles will always remain.

To our purpose, we take a random "explorating point" $$X=(x,y)$$, uniformly distributed on $$Q$$, and compute the probability that it falls outside of any of the coins, which is the ratio $$A/|Q| = A/4$$.
That is equivalent to fix a circle of radius $$r$$ around the explorating point given to be at $$X \in [x, x+dx) \times [y+dy) \subset Q$$, and determine the probability that all the $$n$$ center points $$(x_k,y_k)$$ fall outside of it and within $$R$$.

Let's call $$\lambda(x,y,r)$$ the ratio of the area of the portion of the disc surrounding $$(x,y)$$ that falls inside $$R$$, wrt the area of the entire disc..
We defer to the following step its formulation.

Given $$\lambda \left( {x,y,r} \right)$$ we will then express the area left free for allocating the $$X_k$$ as $$\left| R \right| - \lambda \left( {x,y,r} \right)\pi r^{\,2}$$, whose ratio to $$|R|$$ is $$P(x,y,r) = 1 - {{\lambda \left( {x,y,r} \right)\pi r^{\,2} } \over {4\left( {1 - r} \right)^{\,2} }}$$ being that the probability of finding a single $$X_k$$ out of the circle in $$X$$, i.e. $$\Pr \left( {r < \left| {X_k - X} \right|\;\left| {\;X} \right.} \right) = P(x,y,r) = 1 - {{\lambda \left( {x,y,r} \right)\pi r^{\,2} } \over {4\left( {1 - r} \right)^{\,2} }}$$ The probability of finding there all the $$n$$ points then will be $$P(x,y,r)^n$$, finally turning into the expected value of the free area, will be \bbox[lightyellow] { \eqalign{ & E\left( {{{A(n,r)} \over {\left| Q \right|}}} \right)= \overline A (n,r) = \cr & = \int\!\!\!\int\limits_{X \in Q} {\Pr \left( {r < \min \left( {\left| {X_k - X} \right|\;\, \left| {\,k \in \left[ {1,n} \right]} \right.} \right)\;\left| {\;X} \right.} \right)\Pr \left( {dX} \right)} = \cr & = \int_{ - 1}^1 {\int_{ - 1}^1 {\left( {1 - {{\lambda \left( {x,y,r} \right)\pi r^{\,2} } \over {4\left( {1 - r} \right)^{\,2} }}} \right)^{\,n} {{dxdy} \over 4}} } = \cr & = \int_0^1 {\int_0^1 {\left( {1 - {{\lambda \left( {x,y,r} \right)\pi r^{\,2} } \over {4\left( {1 - r} \right)^{\,2} }}} \right)^{\,n} dxdy} } \cr} \tag{1} } where the last step comes from the symmetry of $$\lambda$$.

2) Computational aspects

The exact general formulation of $$\lambda (x,y,r)$$ is quite cumbersome, being heavily piecewise fragmented according to the various relative positions of the circle and the square.

However, to the scope of finding a good asymptotic approximation for large $$n$$ and small $$r$$, we can start from the simpler version which is obtained

in the case that $$r \le 1/2$$.

In this case the exact formula is, within the first quadrant

$$\bbox[lightyellow] { \left\{ \begin{array}{l} u = \left( {x - \left( {1 - r} \right)} \right)/r\quad v = \left( {y - \left( {1 - r} \right)} \right)/r \\ 0 \le x,y \le 1\quad \Leftrightarrow \quad 1 - \frac{1}{r} \le u,v \le 1 \\ g(t) = \left[ {t < - 1} \right]\left( { - \frac{\pi }{2}} \right) + \left[ { - 1 \le t < 1} \right] \left( {\arcsin t + t\sqrt {1 - t^{\,2} } } \right) + \left[ {1 \le t} \right]\left( {\frac{\pi }{2}} \right) \\ \lambda (u,v) = \frac{1}{{2\pi }}\left\{ {\begin{array}{*{20}c} {\frac{\pi }{2} + 2uv - g(u) - g(v)} & {\left| {\;u^{\,2} + v^{\,2} < 1} \right.} \\ { - 2g(u) - 2g(v)} & {\left| {\;u < 0\; \wedge \;v < 0\; \wedge \;1 \le u^{\,2} + v^{\,2} } \right.} \\ {\pi - 2g(v)} & {\left| {\;u < 0\;\; \wedge \;0 \le v\,\; \wedge \;1 \le u^{\,2} + v^{\,2} } \right.} \\ {\pi - 2g(u)} & {\left| {\;0 \le u\; \wedge \;v < 0\; \wedge \;1 \le u^{\,2} + v^{\,2} } \right.} \\ 0 & {\left| {\;0 \le u\;\; \wedge \;0 \le v\,\; \wedge \;1 \le u^{\,2} + v^{\,2} } \right.} \\ \end{array}} \right. \\ \end{array} \right. \tag{2} }$$

where $$[P]$$ denotes the Iverson bracket.
In particular it is $$\bbox[lightyellow] { \lambda (u,v) = 1\quad \left| {\;\left( {1 - 1/r} \right) \le u < -1\; \; \wedge \;\left( {1 - 1/r} \right) \le v < -1} \right. \tag{2.a} }$$

Now $$\lambda$$ is essentially a smoothed 2D step function in $$[1-1/r,\; 1]^2$$,

so it is possible to demonstrate that, with an error negligible to our scope (less than $$0.014$$ only in the corner$$[-1,1]^2$$), we can approximate it as the product of its cross-sections in $$u$$ and $$v$$, i.e. of the third and fourth lines above.
And, as a further profitable approximation , we can "bevel" the corner $$-1 < u,v <1$$ radially with the same profile as in the "flanks", that is we can approximate $$\lambda$$ as $$\bbox[lightyellow] { \left\{ \matrix{ \matrix{ {u = \left( {x - \left( {1 - r} \right)} \right)/r \quad v = \left( {y - \left( {1 - r} \right)} \right)/r} \hfill \cr {0 \le x,y \le 1\quad \Leftrightarrow \quad 1 - {1 \over r} \le u,v \le 1} \hfill \cr {h(t) = {1 \over \pi }\left( {\arccos t - t\sqrt {1 - t^{\,2} } } \right)} \hfill \cr {\rho = \sqrt {\left( {u + 1} \right)^2 + \left( {v + 1} \right)^2 } } \hfill \cr } \hfill \cr \lambda (u,v) \approx \left\{ {\matrix{ 1 \hfill & {\left| {\;u < - 1\;,\quad v < - 1} \right.} \hfill \cr {h(v)} \hfill & {\left| {\;u < - 1\;,\quad - 1 \le v \le 1\,} \right.} \hfill \cr {h(u)} \hfill & {\left| {\; - 1 \le u \le 1\;,\quad v < - 1\,} \right.} \hfill \cr {h(\rho - 1)} \hfill & {\left| {\; - 1 \le u,\quad - 1 \le v, \quad \left( {u + 1} \right)^2 + \left( {v + 1} \right)^2 < 4} \right.} \hfill \cr 0 \hfill & {\left| {\;4 \le \left( {u + 1} \right)^2 + \left( {v + 1} \right)^2 } \right.} \hfill \cr } } \right. \hfill \cr} \right. \tag{3} }$$ Then , putting $$H(r) = {{\pi r^{\,2} } \over {4\left( {1 - r} \right)^{\,2} }}$$ we can rewrite the integral in (1) as \bbox[lightyellow] { \eqalign{ & \overline A (n,r) = \cr & = \int_0^1 {\int_0^1 {\left( {1 - \lambda \left( {x,y,r} \right)H(r)} \right)^{\,n} dxdy} } = \cr & = r^{\,2} \int_{1 - 1/r}^1 {\int_{1 - 1/r}^1 {\left( {1 - \lambda \left( {u,v} \right)H(r)} \right)^{\,n} dudv} } = \cr & = r^{\,2} \int_{1 - 1/r}^{ - 1} {\int_{1 - 1/r}^{ - 1} {\left( {1 - \lambda \left( {u,v} \right)H(r)} \right)^{\,n} dudv} } + \cr & + 2r^{\,2} \int_{1 - 1/r}^{ - 1} {\int_{ - 1}^1 {\left( {1 - \lambda \left( {u,v} \right)H(r)} \right)^{\,n} dudv} } + \cr & + r^{\,2} \int_{ - 1}^1 {\int_{ - 1}^1 {\left( {1 - \lambda \left( {u,v} \right)H(r)} \right)^{\,n} dudv} } = \cr & = \left( {1 - H(r)} \right)^{\,n} \left( {1 - 2r} \right)^{\,2} + \cr & + 2r\left( {1 - 2r} \right)\int_{ - 1}^1 {\left( {1 - h(u)H(r)} \right)^{\,n} du} + \cr & + r^{\,2} \int_{ - 1}^1 {\int_{ - 1}^1 {\left( {1 - \lambda \left( {u,v} \right)H(r)} \right)^{\,n} dudv} } = \cr & = L(n,r) + 2r\left( {1 - 2r} \right)I(n,r) + r^{\,2} J(n,r) \cr} \tag{4} }

From this exact expression we can start and apply the most appropriate approximation for the intended values of $$n, r$$ and for the required accuracy.

• after some time ... Commented Nov 1, 2021 at 15:40