Área esperada cubierta por círculos dentro de un cuadrado

Question

$n$ círculos de radio $r$ se colocarán al azar dentro de un cuadrado de lado $l$ . ¿Cuál es la superficie que se espera que encierren los círculos?

Edición: Como sugirió @Mirko, definimos la colocación aleatoria de los círculos eligiendo puntos de un cuadrado de lado $l-2r$ concéntricas a la inicial a partir de una distribución uniforme y utilizando cada una de ellas como centro de un círculo específico.

El problema al que me enfrento es que no sé cómo contabilizar estadísticamente los solapamientos con los círculos. He intentado dividir el cuadrado en pequeñas "celdas" cuadradas de lado $2r$ de manera que cada círculo pueda existir en una de las celdas y obtuvo una expresión para la probabilidad de $k$ círculos para que existan sin solaparse. Sin embargo, este enfoque subestima drásticamente la probabilidad real, ya que no tiene en cuenta los círculos que existen entre las celdas.
Cualquier enfoque alternativo sería muy apreciado.

Answer 1

Así que estamos asumiendo $l\ge2r$ . Tomemos el cuadrado en coordenadas cartesianas como $S:=[-l/2,\,l/2]^2$ . El punto $(x,\,y)$ en ella cae dentro de un círculo centrado en $(u,\,v)\in S^\prime:=[-(l/2-r),\,l/2-r]$ si $$(x-u)^2+(y-v)^2\le r^2.$$ Dejemos que $f(x,\,y)$ denotan la probabilidad de esto cuando tomamos $U,\,V$ a ser IIDs uniformes en su soporte; el mismo tratamiento de $X,\,Y$ hace que la probabilidad de que un punto aleatorio se encuentre en al menos uno de los círculos $$1-\int_S(1-f)^ndxdy,$$ así que multiplicando esto por $\pi l^2$ da el área media de la unión de los círculos. Obsérvese el $n\to\infty$ es inferior a $\pi l^2$ porque algunos puntos tienen $f=0\implies\lim_{n\to\infty}(1-f)^n=1$ . En particular, un punto en $S$ puede ser hasta $r\sqrt{2}$ desde el punto más cercano en $S^\prime$ .

Así que ahora tenemos dos tareas: calcular $f$ , entonces calcula $\int_S(1-f)^ndxdy$ . Nota $f$ es la proporción del área de $S^\prime$ a una distancia $r$ de $(x,\,y)$ . Mientras se obtiene $f$ como una función a trozos es factible, sospecho que las integrales son numéricas para grandes $n$ .

Answer 2

1. el enfoque geométrico

El problema es claramente invariable a escala.
Así que tomemos el cuadrado $Q=[-1,1]^2$ en cuyo interior yacía $n$ "monedas" de radio $r \le 1$ , que también pueden solaparse.

Las monedas están distribuidas aleatoriamente i.i.d. de manera uniforme, con centros $X_k=(x_k,y_k)$ en el cuadrado $R =[ -1+r,1-r]^2$ .
Queremos determinar el área prevista $A$ del espacio que queda sin cubrir en $Q$ que es el complemento de la unión del $n$ monedas. La superficie puede variar de un máximo de $4- \pi r^2$ cuando las monedas estén totalmente apiladas, hasta $4-n \pi r^2$ si el espacio lo permite colocar las monedas sin que se superpongan, y luego ,al aumentar de $n$ y/o $r$ al máximo embalaje , hasta llegar a $n$ a un mínimo de $(4-\pi) r^2$ cuando el cuadrado está casi totalmente cubierto, excepto en las esquinas donde el espacio con los círculos tangentes permanecerá siempre.

Para nuestro propósito, tomamos un "punto exploratorio" aleatorio $X=(x,y)$ distribuido uniformemente en $Q$ y calcular la probabilidad de que caiga fuera de cualquiera de las monedas, que es el cociente $A/|Q| = A/4$ .
Eso equivale a fijar un círculo de radio $r$ alrededor del punto de exploración dado a $X \in [x, x+dx) \times [y+dy) \subset Q$ , y determinar la probabilidad de que todos los $n$ puntos centrales $(x_k,y_k)$ caen fuera de ella y dentro $R$ .

Llamemos $\lambda(x,y,r)$ la relación entre el área de la porción del disco que rodea $(x,y)$ que cae dentro $R$ con respecto al área de todo el disco
Aplazamos al siguiente paso su formulación.

Dado $\lambda \left( {x,y,r} \right)$ expresaremos entonces el área que queda libre para asignar el $X_k$ como $\left| R \right| - \lambda \left( {x,y,r} \right)\pi r^{\,2}$ cuya relación con $|R|$ es $$ P(x,y,r) = 1 - {{\lambda \left( {x,y,r} \right)\pi r^{\,2} } \over {4\left( {1 - r} \right)^{\,2} }} $$ siendo que la probabilidad de encontrar un $X_k$ fuera del círculo en $X$ es decir $$ \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} }} $$ La probabilidad de encontrar allí todos los $n$ puntos serán entonces $P(x,y,r)^n$ , convirtiéndose finalmente en la esperada del área libre, será $$ \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} }$$ donde el último paso proviene de la simetría de $\lambda$ .

2) Aspectos computacionales

La formulación general exacta de $\lambda (x,y,r)$ es bastante engorroso, ya que está muy fragmentado según las distintas posiciones relativas del círculo y el cuadrado.

Sin embargo, al alcance de encontrar una buena aproximación asintótica para grandes $n$ y pequeños $r$ podemos partir de la versión más sencilla que se obtiene

en el caso de que $r \le 1/2$ .

En este caso, el fórmula exacta es, dentro del primer cuadrante

$$ \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} }$$

donde $[P]$ denota el Soporte Iverson .
En particular $$ \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} }$$

Ahora $\lambda$ es esencialmente una función escalonada 2D suavizada en $[1-1/r,\; 1]^2$ ,

por lo que es posible demostrar que, con un error despreciable para nuestro ámbito (inferior a $0.014$ sólo en la esquina $[-1,1]^2$ ), podemos aproximarla como el producto de sus secciones transversales en $u$ y $v$ es decir, de las líneas tercera y cuarta anteriores.
Y, como una aproximación más rentable , podemos "biselar" la esquina $-1 < u,v <1$ radialmente con el mismo perfil que en los "flancos", es decir, podemos aproximar $\lambda$ como $$ \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} }$$ Entonces, poniendo $$ H(r) = {{\pi r^{\,2} } \over {4\left( {1 - r} \right)^{\,2} }} $$ podemos reescribir la integral en (1) como $$ \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} }$$

De esta expresión exacta podemos partir y aplicar la aproximación más adecuada para los valores previstos de $n, r$ y para la precisión requerida.