¿Cuál es la profundidad convexa esperada de un conjunto de $m$ puntos elegidos al azar en el cuadrado unitario?

Question

Definición. Sea $X$ un conjunto de puntos en $\mathbb{R}^2$. Entonces la secuencia de vértices de $X$ se define por

1. $X_{0}=X$, y
2. $X_{i+1}=\left\{x\in \operatorname{Conv}(X_{i}): x \notin \operatorname{Conv}(X_{i}\setminus\{x\})\right\}$.

La profundidad convexa de $X$ es el menor $k\in \mathbb{N}$ tal que $X_{k}$ es vacío.

Aquí hay un ejemplo donde $|X|=30$.

Mi pregunta es,

¿Cuál es la profundidad convexa esperada de un conjunto de $m$ puntos elegidos al azar en el cuadrado unitario?

La respuesta debería ser una función de $m$. He simulado algunos datos para esto, mostrados a continuación, donde el eje $x$ es $m$ y el eje $y$ es la media de la profundidad convexa. Parece ser algo cercano a $\sqrt{m}$ (o tal vez algo más cercano a $m^{3/2}$, como sugiere el enlace de lhf en los comentarios). Aunque no estoy seguro de cómo demostrarlo.

.

Answer 1

Si tomamos que la distancia mínima promedio entre dos puntos para N puntos distribuidos uniformemente en un círculo unitario se aproxima para N grande por: $\langle{d}\rangle=\frac{1}{\sqrt{2}N}$

Entonces puedes imaginar un círculo unitario con un número bastante grande de puntos N y un número $m_\delta$ de secuencias de vértices. Supongamos que agregamos un anillo concéntrico de ancho exactamente $\langle{d}\rangle$ alrededor del círculo unitario para aumentar el número de puntos en $N_\delta=pA$. Donde $p=\frac{N}{\pi}$ es la densidad de área de puntos y A es el área del anillo. Así que $N_\delta = (\sqrt{2} + \frac{1}{2N})/\pi$

Dado que hemos elegido un ancho de anillo exactamente igual a la distancia promedio mínima entre puntos, es fácil ver que obtendríamos dos nuevas secuencias de vértices convexos en promedio dentro de este nuevo anillo. Puedes entender esto imaginando que hay muchos puntos dentro de este anillo muy delgado pero solo cada otro punto dará un punto de vértice convexo, los otros, aunque aún están en el anillo, darán la siguiente secuencia de vértices "más pequeña".

Ahora imagina que aumentamos el radio del círculo unitario a 2 pero mantenemos la misma densidad de puntos p en general. El área del círculo se cuadriplica, por lo que ahora tenemos ~$4N$ puntos en el nuevo círculo. También hemos agregado algún número total de nuevas secuencias de vértices $m_\delta$. Ahora tenemos un número total de secuencias de vértices $m_2=m_1+m_\delta=m_1+\sqrt{8}N$

Así que ahora tenemos un total de $m_2$ secuencias de vértices en el círculo unitario 2 para un total de 4N puntos. Si aumentamos el radio a 3 obtenemos: $m_3=m_1+2m_\delta=m_1+2\sqrt{8}N$...y así sucesivamente: $$m_k=m_1+k\sqrt8N$$

Mientras que el número total de puntos en el radio k es $$N_k=Nk^2$$ Entonces vemos que $$m_k(N_k)=m_1+\sqrt\frac{8N_k}{N}N=m_1+\sqrt{8p\pi*N_k}$$

$m_1$ se convierte en una constante que depende de p, la densidad original de puntos. Así que para N grande, es una función cuadrada.

Para un cuadrado se podría aplicar el mismo argumento, pero con N grande debería converger hacia la misma respuesta a medida que te mueves hacia el centro del cuadrado. Creo que con el cuadrado obtienes que las secuencias de vértices convexos convergen hacia una forma unitaria: $$x^t+y^t=1^t$$ que en el $\lim_{t\to\infty}$ se convierte en un cuadrado.

Answer 2

Es $m^{2/3}$. Ver Ketan Dalal, Contando la cebolla, Random Struct. Alg., 24 (2004), 155–165, doi:10.1002/rsa.10114.