Un cuadrado contiene muchos puntos aleatorios. Desde cada punto, un disco crece hasta que choca con otro disco. ¿Qué proporción del cuadrado está cubierta por los discos?

Question

Una lámina cuadrada contiene $n$ puntos independientes elegidos uniformemente al azar. En un momento dado, cada punto se convierte en el centro de un disco cuyo radio crece desde $0$, digamos a $1$ cm por segundo, y se detiene de crecer cuando el disco choca con otro disco.

Considera los discos después de que todo el crecimiento se detiene. Aquí hay un ejemplo con $n=20$.

Sea $P=$ la proporción de la cuadrada que está cubierta (es decir, ocupada) por los discos. En el ejemplo anterior, $P\approx0.383$.

¿A qué se acerca $P$ cuando $n\to\infty$?

La forma de la lámina (por ejemplo, cuadrada) no importa, ya que estamos tomando $n\to\infty$. La tasa de crecimiento (por ejemplo, $1$ cm por segundo) no importa, siempre y cuando todos los discos comiencen a crecer al mismo tiempo y crezcan a la misma velocidad.

Mis pensamientos

Intenté encontrar la probabilidad de que un nuevo punto aleatorio en la cuadrada se encuentre dentro de uno de los discos existentes. También intenté encontrar el área promedio de un disco. Pero no he tenido éxito. Estas preguntas parecen complicadas por el hecho de que el tamaño del disco de un punto está determinado no solo por la distancia del punto a sus vecinos, sino también por las distancias de sus vecinos a sus vecinos, y así sucesivamente.

Contexto

Esta pregunta fue inspirada por otra pregunta, "Un disco contiene $n$ puntos aleatorios. Cada punto está conectado a su vecino más cercano. ¿A qué se acerca el tamaño promedio del grupo cuando $n\to\infty$?". Ambas preguntas son sobre propiedades inherentes del proceso de Poisson en $2D$.

Answer 1

Hice una búsqueda de literatura y encontré que:

1. La pregunta de OP corresponde exactamente a lo que se llama modelo de lilypond introducido por Häggström y Meester (1996). Daley et al. (1999) estudiaron independientemente el mismo modelo y reportaron una estimación de Monte-Carlo de la proporción límite con $$ \text{media} = 0.3487 \qquad\text{y}\qquad \text{DE} = 0.00045 $$ usando $10^6$ muestras.

2. Parece que la pregunta de OP aún no ha sido respondida en la literatura, lo cual no es sorprendente considerando que las propiedades estadísticas de una función geométrica de un modelo de percolación en continua son notoriamente difíciles de responder, si no imposibles.

3. Interesantemente, la versión en 1D de la pregunta de OP tiene una respuesta definitiva: $$P_{\text{1D,limite}} = 1 - e^{-1}$$ Ver la Sección 6 de Daley et al. (1999), por ejemplo.

---

Referencias.

• O. Häggström, y R. Meester. “Nearest Neighbor and Hard Sphere Models in Continuum Percolation.” Random Structures & Algorithms 9, no. 3 (1996): 295–315.

• D. J. Daley, H. Stoyan, y D. Stoyan. “The Volume Fraction of a Poisson Germ Model with Maximally Non-Overlapping Spherical Grains.” Advances in Applied Probability 31, no. 3 (1999): 610–24.

Answer 2

Adjunto un script de MATHEMATICA que genera un conjunto de círculos aleatorios según sea necesario. El proceso de cálculo podría ser más eficiente, pero también sería menos transparente.

data = {{1.0032, 0.1304},{0.8713, 0.0446}, {0.8458,0.2497}, 
{0.6789, 0.2751}, {0.6137, 0.2179}, 
{0.5437, 0.1209}, {1.0398, 0.5311}, 
{1.0525, 0.6202}, {0.8347, 0.5502}, 
{0.8061, 0.6297}, {0.7202, 0.6170}, 
{0.6487, 0.7219}, {0.6964, 0.7839}, 
{0.8442, 0.9461}, {0.0763, 0.2990}, 
{0.1160, 0.5915}, {0.2941, 0.5979}, 
{0.2305, 0.7871},{0.1717, 0.8078}, 
{0.0556,0.9334}};
boundary = {{0.0270, 0.0250}, {1.0764, 0.0250}, 
{1.0780, 1.0744}, {0.0238,1.0744}, {0.0270,0.0250}};

(************************************)
SeedRandom[1];
data = RandomReal[{-1, 1}, {200, 2}];
boundary = {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}, {-1, -1}};
(************************************)

{X, Y} = Transpose[boundary];
xmin = Min[X];
xmax = Max[X];
ymin = Min[Y];
ymax = Max[Y];
n = Length[data];

gr1 = ListPlot[data, PlotStyle -> Black];
gr2 = ListLinePlot[boundary, PlotStyle -> Thick];

circs = Table[{data[[k]], 0, 0}, {k, 1, n}];
For[i = 1, i <= n, i++, 
 For[j = i + 1, j <= n, j++, 
  dist[i, j] = Norm[circs[[i, 1]] - circs[[j, 1]]]]]

minDist[circs_] := Module[{n = Length[circs], d, dmin = Infinity, pi, pj, i, j, i0, j0},
  For[i = 1, i <= n, i++,
   For[j = i + 1, j <= n, j++, 
     If[circs[[i, 3]] == 1 && circs[[j, 3]] == 1, Continue[]];
     d = dist[i, j] - circs[[i, 2]] - circs[[j, 2]];
     If[d <= dmin,
      dmin = d;
      pi = circs[[i]];
      pj = circs[[j]];
      i0 = i;
      j0 = j];
     ];
   ]; Return[{dmin, i0, j0, pi, pj}]
  ]

dmin = 0;
grs = {};
While[dmin < Infinity,
  {dmin, i0, j0, pi, pj} = minDist[circs];
  If[dmin == Infinity, Continue[]];
  If[pi[[3]] == 0 && pj[[3]] == 0,
   circs[[i0, 2]] += dmin/2;
   circs[[j0, 2]] += dmin/2;
   circs[[i0, 3]] = 1;
   circs[[j0, 3]] = 1;
   For[k = 1, k <= n, k++,
    If[circs[[k, 3]] != 1, circs[[k, 2]] += dmin/2]
    ]];
  If[circs[[i0, 3]] == 1 && circs[[j0, 3]] == 0,
   circs[[j0, 2]] += dmin;
   circs[[j0, 3]] = 1;
   For[k = 1, k <= n, k++,
    If[circs[[k, 3]] != 1, circs[[k, 2]] += dmin]]
   ];
  If[circs[[j0, 3]] == 1 && circs[[i0, 3]] == 0,
   circs[[i0, 2]] += dmin;
   circs[[i0, 3]] = 1;
   For[k = 1, k <= n, k++,
    If[circs[[k, 3]] != 1, circs[[k, 2]] += dmin]]
   ];
  grcircs = Table[Graphics[{Blue, Disk[circs[[k, 1]], circs[[k, 2]]]}, PlotRange -> {{xmin, xmax}, {ymin, ymax}}, PlotRangeClipping -> True], {k, 1, n}];
  AppendTo[grs, grcircs];
  ];

Show[grs, gr1, gr2, PlotRange -> {{xmin, xmax}, {ymin, ymax}}, PlotRangeClipping -> True]

La configuración propuesta.

Una configuración aleatoria

Me parece que la máxima razón se logra con una estructura tipo panal de abejas, yendo al límite. A partir de Lagrange $\frac{\pi}{2\sqrt{3}}$.